Number Theory • Topic 3

Prime Factorization

Any integer greater than 1 is either prime or can be written as a product of primes. This decomposition reveals the "DNA" of the number.

Canonical Representation

Definition (Canonical Form)

Every integer

n > 1

can be written uniquely as:

n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}

where

p_{1} < p_{2} < \dots < p_{k}

are primes and

e_{i} \geq 1

are exponents.

n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}

, the number of divisors

τ (n)

(or

d (n)

) is:

τ (n) = (e_{1} + 1) (e_{2} + 1) \dots (e_{k} + 1)

The sum of divisors

σ (n)

is:

σ (n) = \frac{p _{1}^{e_{1} + 1} - 1}{p _{1} - 1} \cdot \frac{p _{2}^{e_{2} + 1} - 1}{p _{2} - 1} \dots \frac{p _{k}^{e_{k} + 1} - 1}{p _{k} - 1}

An integer

n

is a perfect square if and only if all exponents

e_{i}

in its prime factorization are even.

Exercise (Problem 1)

Find the smallest positive integer with exactly 12 divisors.

Exercise (Problem 2)

Prove that the product of the divisors of

n

n^{τ (n) /2}

Exercise (Problem 3)

Determine the number of zeros at the end of

2023!