The elementary bricks of the integers

The fundamental theorem of arithmetic

The result that justifies the word "prime": every integer is built from them, and in only one way.

The statement

Fundamental theorem of arithmetic. Every integer n ≥ 2 can be written as a product of primes, and this writing is unique up to the order of the factors.

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5

Two distinct claims hide in there, and the second is by far the harder:

EXISTENCE : every integer factors        (easy, by induction)
UNIQUENESS: in only one way              (hard, rests on Euclid's lemma)

Finding the factorisation

Divide by successive primes, restarting from the smallest each time:

   360 | 2
   180 | 2
    90 | 2
    45 | 3
    15 | 3
     5 | 5
     1
                ->  360 = 2³ × 3² × 5

What the factorisation reveals

Once factored, an integer surrenders all its multiplicative properties.

The number of divisors is obtained by adding 1 to each exponent and multiplying:

360 = 2³ × 3² × 5¹     ->    (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24 divisors

Each divisor is written 2^a × 3^b × 5^c with a ∈ {0,1,2,3}, b ∈ {0,1,2}, c ∈ {0,1}: the multiplication principle of counting.

GCD and LCM are read off by comparing exponents:

   360 = 2³ × 3² × 5
    84 = 2² × 3  × 7

GCD: keep the SMALLEST common exponent   ->  2² × 3 = 12
LCM: keep the LARGEST exponent           ->  2³ × 3² × 5 × 7 = 2520

And the general relation GCD × LCM = a × b checks out: 12 × 2520 = 30,240 = 360 × 84.

Divisibility becomes a comparison of exponents: a divides b if and only if each exponent of a is at most that of b.

The practical limit

Factoring is easy to describe and very expensive to do. Nobody knows how to factor a 600-digit integer quickly:

multiplying two 300-digit primes            ->  instantaneous
recovering those two factors from the product -> out of reach

This asymmetry is not a technical detail: it is the foundation of RSA encryption, which today protects most encrypted communication. Security rests entirely on the fact that no fast factoring algorithm is known — which has not been proved impossible.

Summary