Prime factorization — factor trees, ladder method

1.1.9 · Maths › Arithmetic & Number Systems

WHY — ye matter kyun karta hai?

WHAT — hum actually kar kya rahe hain?

HOW — Method 1: The Factor Tree

Figure — Prime factorization — factor trees, ladder method

HOW — Method 2: The Ladder (Division) Method

Worked example

$60$ ke liye Ladder Hamesha sabse chote prime se shuru karo: $2$ , phir $3$ , phir $5$ , phir $7 \dots$

 2 | 60
 2 | 30
 3 | 15
 5 |  5
   |  1   ← jab 1 aaye tab ruko

2 se shuru kyun? $60$ even hai → $2$ se divisible hai. Jab tak even ho, $2$ se divide karte raho.
3 par kyun aaye? $15$ odd hai, $2$ se divisible nahi; sabse chota prime jo $15$ ko divide karta hai woh $3$ hai.
1 par kyun rukna? Jab quotient $1$ ho jaaye, koi factors nahi bache.
Left side ke primes: $2, 2, 3, 5$ . $60 = 2^{2} \cdot 3 \cdot 5$

Worked example

$84$ ke liye Ladder (poora walk-through)

$84$ even → ÷2 se $42$ milta hai. Kyun? Even numbers hamesha $2$ ka factor lete hain.
$42$ even → ÷2 se $21$ milta hai. Ab $21$ odd hai, 2 se divide karna band karo.
$21 = 3 \times 7$ : ÷3 se $7$ ; ÷7 se $1$ . $84 = 2^{2} \cdot 3 \cdot 7$

Worked example Prime-heavy number

$198$ ke liye Ladder

Aakhir mein 11 kyun? $11$ prime hai aur sirf khud se divisible hai. $198 = 2 \cdot 3^{2} \cdot 11$

Factorization ka use (asli payoff)

Forecast-then-Verify drill

Recall Dekhne se pehle predict karo

Q: $360$ ko factorize karo. Pehle $2, 3, 5$ ke exponents forecast karo. Verify (ladder):

 2 | 360    2 | 180    2 | 90    3 | 45    3 | 15    5 | 5    | 1

$360 = 2^{3} \cdot 3^{2} \cdot 5$ Divisors $= (3 + 1) (2 + 1) (1 + 1) = 24$ . Kya tumne $2^{3} \cdot 3^{2} \cdot 5$ likha? Agar tumne $2^{2}$ likha, toh dobara count karo kitni baar $360$ even hai ( $360 \to 180 \to 90$ = teen halvings).

Common mistakes (Steel-manned)

Mnemonic

Feynman: 12-saal ke bachche ko explain karo

Recall Simply explain karo (hidden)

Socho har number ek LEGO castle hai. Kuch blocks chote blocks mein tod sakte hain, lekin prime blocks ( $2, 3, 5, 7 \dots$ ) aur nahi toot sakte — ye sabse tiny pieces hain. Prime factorization matlab apna castle tab tak todna jab tak sirf ye tiny LEGO pieces table par na hon. Cool magic yeh hai: chahe tum kisi bhi tarah se todein (tree method) ya ek ek step carefully (ladder method), tumhe hamesha exactly same pile of tiny blocks milti hai. Yeh "har baar same pile" wala rule hi math ko itna clean banata hai.

Active-Recall Flashcards

1 prime number kyun nahi hai?

Ek prime mein exactly do distinct divisors hone chahiye (1 aur khud woh); 1 ka sirf ek divisor hai, isliye woh unit hai, prime nahi.

Fundamental Theorem of Arithmetic batao.

Har integer >1 primes ka product hota hai, aur woh factorization unique hoti hai sivaay factors ke order ke.

60 ko prime-factorize karo.

2^{2} \cdot 3 \cdot 5

84 ko prime-factorize karo.

2^{2} \cdot 3 \cdot 7

Ladder method mein kab rukna chahiye?

Jab quotient 1 ban jaaye.

Factor tree mein kaunse nodes leaves hote hain?

Prime numbers (unhe aur split nahi kiya ja sakta).

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

ke divisors ki count ka formula?

d (n) = (a_{1} + 1) (a_{2} + 1) \dots (a_{k} + 1)

Prime powers se HCF aur LCM kaise nikaalte hain?

HCF = primes ka product min exponent par; LCM = max exponent par.

60 aur 84 ka HCF aur LCM primes se compute karo.

HCF

= 2^{2} \cdot 3 = 12

; LCM

= 2^{2} \cdot 3 \cdot 5 \cdot 7 = 420

Ladder mein pehle kaunsa prime test karna chahiye?

Sabse chota, 2 (jab tak even ho divide karte raho), phir 3, 5, 7...

Alag factor trees same answer kyun dete hain?

Unique factorization (FTA) ki wajah se — prime leaves ka multiset fixed hota hai.

360 = 2^{3} \cdot 3^{2} \cdot 5

ke kitne divisors hain?

(3 + 1) (2 + 1) (1 + 1) = 24

Connections

HCF and LCM — directly in-hi prime powers se compute hote hain (min/max exponents).
Divisibility Rules — decide karte hain ki ladder mein aage kaunsa prime divide karega.
Fundamental Theorem of Arithmetic — guarantee karta hai ki answer unique hai.
Simplifying Fractions — numerator & denominator ke shared prime factors cancel karo.
Number of Divisors — exponent-plus-one formula use karta hai.
Sieve of Eratosthenes — woh prime "alphabet" generate karta hai jise tum test mein use karte ho.