fundamentaltheoremofarithmetic

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]