Fundamental Theorem of Arithmetic

This theorem guarantees that the prime factorization of any integer is unique. It is the reason we can talk about "the" factorization of a number.

Statement

Theorem (Fundamental Theorem of Arithmetic)

Every integer

n > 1

can be represented as a product of prime numbers in exactly one way, up to the order of the factors.

In other number systems (like

Z [- 5]

), unique factorization fails. Example:

6 = 2 \cdot 3 = (1 + - 5) (1 - - 5)

Existence: Induction. If $n$ is prime, done. If composite, $n = ab$ . Factors $a, b$ decompose further until primes are reached.
Uniqueness: Uses Euclid's Lemma ( $p ∣ ab ⟹ p ∣ a$ or $p ∣ b$ ).

GCD and LCM: Can be computed by taking min/max of exponents in prime factorization.
Irrationality: Used to prove $2$ is irrational (by comparing powers of 2 in $a^{2} = 2 b^{2}$ ).

Exercise (Problem 1)

a^{2}

is divisible by

b

, and

b^{2}

is divisible by

a

, prove that

a = b

? (False. Find a counterexample). What if we consider square-free parts?

Exercise (Problem 2)

Find all positive integers

a, b, c

such that

a^{b}

divides

b^{c}

and

b^{c}

divides

c^{a}

and

c^{a}

divides

a^{b}

Exercise (Problem 3)

Prove

lo g_{10} 2

is irrational using unique factorization.