Carlos Moreno <firstname.lastname@example.org> wrote: >Chip Eastham wrote: (*edited and corrected*) >> >> One can set aside the theory of primes and give a direct >> proof by induction, based on 1 + 2 = 3. From this clearly >> 3 does not divide 2 = 2^1, so that's the basis step. >> Suppose 3 does not divide 2^k (the induction hypothesis). >> >> Then from 3 - 2 = 1, we multiply both sides by 2^k: >> >> k k k >> 3 2 - 2 2 = 2
i.e. 3 | 3 C & 2 C -> 3|C (= 3C-2C), above C = 2^k
This is a very special case of Euclid's Lemma as I show below.
> Niiiiiceeee!!!! > > It's always refreshing seeing some "unconventional thinking" > that puts aside the obvious ("the obvious" in this case being > the fundamental theorem of arithmetic) to come up with a simple, > nice, refreshing proof like the above.
But, in fact, this proof is an obvious specialization of the key Euclid's Lemma employed to prove the FTA = unique factorization:
LEMMA (Euclid) (a,b)=1 & a|bc -> a|c
PROOF Recall (a,b)=1 -> ja+kb = 1 for some integers j,k
Therefore it follows that a|(ja+kb)c = c [via a|ja, a|bc ] QED
For a,b = 3,2: 3|2c -> 3|( 3 -2)c = c [here j=1, k=-1 ]
k k+1 k k-1 For c = 2 : 3|2 -> 3|2 (-> 3|2 ->...-> 3|1 -><- )
The inference a|bc -> a|(a,b)c is ubiquitous in divisor theory
of the rational integers (or any PID), e.g. see my prior posts .
Note, however, for a fixed prime p (such as p = 3 above), one may directly prove the prime divisor property: p|ab -> p|b or p|c by a brute force case analysis of the the finitely many choices for a, b (mod p). For p=3 it amounts to (+-1)(+-1) != 0 (mod 3).