The big number theory class has moved on to prime factorizations and the fundamental theorem of arithmetic. As it happens, though, I've already done a post on that subject.
Looking back at what I wrote then I see that I left out one important detail. I asserted without proof (though I did provide a link) that if a prime divides the product of two other numbers then it had to divide one of the two factors already. The proof of that result requires something that we estblished last week. So let's have a look.
Last week we mentioned that it is a consequence of the Euclidean algorithm that if a and b are integers with
\[
d= \gcd(a,b),
\]
then we can find (possibly negative) integers x and y such that
\[
ax+by=d.
\]
In particular, if a and b are relatively prime then we can find x and y so that
\[
ax+by=1.
\]
Very nice. But how is that helpful?
Now let p be a prime number. We want to show:
\[
\textrm{If} \ p \ | \ ab \ \textrm{then} \ p \ | \ a \ \textrm{or} \ p \ | \ b.
\]
To accomplish that we shall assume that p does not divide a, and show that this implies that p does divide b.
Well then. If p does not divide a then we must have that
\[
\gcd(p,a)=1.
\]
If that is not clear then remember that the only divisors of a prime number are one and the number itself. But since we are assuming that p does not divide a, we know that p cannot be the greatest common divisor in this case. That leaves one as the only possibility.
Since p and a are relatively prime, we can apply our little trick to find x and y so that
\[
ax+py=1.
\]
Multiplying both sides by b produces
\[
abx+bpy=b.
\]
Look carefully at the left-hand side. I claim that we have:
\[
p \ | \ bpy \phantom{xxx} \textrm{and} \phantom{xxx} p \ | \ abx.
\]
The first of those is obvious. The second follows immediately from our assumption that p divides ab. But those two together imply that p divides the left-hand side. It follows that p divides the right-hand side as well, which is exactly what we were trying to show.
Done and done.
- Log in to post comments