2.1 Topics in Number Theory 4

Theorem 2.1.4 (fundamental theorem of arithmetic) Factorization into primes is unique

up to order.

Proof.

We will actually prove that every integer with non-unique factorization has a proper

divisor with non-unique factorization. If there were integers with non-unique factorization,

then eventually we would be reduced to a prime with non-unique factorization, and that

would conradict the fact that it is a prime and thus has no positive divisors other than 1

and itself.

Let n be an integer with non-unique factorization:

n = p1 × p2 ×···×pr

= q1 × q2 ×···×qs ,

where the primes are not necessarily distinct, but where the second factorization is not

simply a reordering of the first. The prime q1 divides n and so it divides the product of

the pi ’s. By repeating this, there is at least one pi which is divisible by q1. If necessary,

reorder the pi ’s so that q1 divides p1. Since p1 is prime, q1 must equal p1. This says that

n = p2 × p3 ×···×pr

q1= q2 × q3 ×···×qs.

Since the factorization of n were distinct, there factorizations of n/q1 must also be distinct.

Therefore n/q1 is proper divisor of n with non-unique factorization.

where the pi are distinct primes, and the ei are positive integers. Furthermore, the

factorization is unique up to rearrangement of factors.

k , where each ei 0 and fi 0,

Theorem 2.1.5 If a = pe1

pe2 2 ···pek 1 pf2 2 ···pfk

k ,b= pf 1then

gcd(a, b)=pmin(e1 ,f1 )

k1 pmin(e2 ,f2 ) 2 ···pmin(ek ,fk )

and

k . lcm(a, b)=pmax(e1 ,f1 )

1 pmax(e2 ,f2 ) 2 ···pmax(ek ,fk )

Example 2.1.5 Let a = 4864 = 28 · 19,b= 4358 = 2 · 7 · 13 · 19. Then gcd(4864, 3458) =

2 · 19 = 38 and lcm(4864, 3458) = 28 · 7 · 13 · 19 = 442624.