Prime factorization: the tree method

Reminder: prime number

A prime number is an integer $\geq 2$ divisible only by 1 and itself.

The first primes: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots$

Tree method

To factor $n$ into primes:

1. Find a prime divisor (try $2$, then $3$, then $5$, $7$, …).
2. Divide, write the quotient.
3. Repeat on the quotient.
4. Stop when the quotient is prime.

Example: factor 60

$60 \div 2 = 30$ $30 \div 2 = 15$ $15 \div 3 = 5$ $5$ is prime.

$60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$

Divisibility tricks

• By 2: ends in $0, 2, 4, 6, 8$.
• By 3: sum of digits divisible by 3.
• By 5: ends in $0$ or $5$.
• By 9: sum of digits divisible by 9.
• By 11: alternating digit sum divisible by 11.

What is it for?

Simplify a fraction: $\dfrac{60}{84} = \dfrac{2^2 \times 3 \times 5}{2^2 \times 3 \times 7} = \dfrac{5}{7}$.

GCD: take common factors with the smallest exponent. $60 = 2^2 \times 3 \times 5$, $84 = 2^2 \times 3 \times 7$ ⇒ $\gcd = 2^2 \times 3 = 12$.

LCM: all factors with the largest exponent. $\text{lcm}(60, 84) = 2^2 \times 3 \times 5 \times 7 = 420$.

Uniqueness

Fundamental theorem of arithmetic: every integer $> 1$ factors uniquely (up to order) as a product of primes.

Common mistakes

1. Missing factors (test each prime carefully).
2. Using a non-prime factor ($60 = 6 \times 10$ is NOT a prime factorization).
3. Confusing GCD and LCM in the exponent rule.

?À toi de jouer

Prime factorization of 72?

A.2³ × 3²B.2² × 3² × 5C.8 × 9D.2⁴ × 3

Valider