Fundamental Theorem of Arithmetic
Every integer n=p1p2p3p4…pk, uniquely
Proof:
Either n prime or composite - if prime, n=p1, if composite n=p1n’
Repeat, with n’ for n, until n=pk, prime remains
Suppose n=p1p2p3p4…pk=q1q2q3q4…qk’
p1|q1q2q3q4…qk’ and q1|p1p2p3p4…pk
p1=qj’ and q1=pj
If primes ordered:
p1>=q1 and q1>=p1
p1=q1
Divide both by p1, leaving n’=p2p3p4…pk=q2q3q4…qk’ and repeat to give pi=qi [all i]