Euclid's Lemma (For Composite Divisors)

As seen from before, we have the following: Given a prime such that $p\mid ab$, we have $p\mid a$ or $p\mid b$.

Since $p$ is a prime, this intuitively makes sense. If it didn't divide both, then there would need to be "parts" of the prime coming from both $a$ and $b$, which means it wouldn't be prime.

So, we wish to generalize, so that $p$ is not necessarily prime. What was nice before was that we couldn't have parts coming from both $a$ and $b$. Thus, we try to recreate that.

Theorem: Given $n$ such that $n\mid ab$, and $\gcd(n,a)=1$, we have $n\mid b$.

This theorem works similarly. If $n\mid ab$, then we have that $a$ and $b$ combine to make a multiple of $n$. However, if $\gcd(n,a)=1$, no part of $n$ must come from $a$. Thus, all parts must come from $b$, so $n\mid b$.

Proof: Since $\gcd(n,a)=1$, by Bezout's Identity there exists integers $x,y$ such that $nx+ay=1$. Multiplying by $b$, we have $nbx+aby=b$. Since $n\mid ab$, we have $n\mid aby$. Thus, $n\mid nbx+aby$. Hence $n\mid b$. $\Box$