Legendre’s formula kya hai?

n! me prime p ki power (exponent) v_p(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ... jab tak p^k ≤ n.

Highest power of a (composite) in n! kaise nikalte hain?

a ko prime factors me tod do: a = p1^e1 p2^e2 ...; phir v_pi(n!) Legendre se nikalo; answer = min( v_p1(n!)/e1, v_p2(n!)/e2, ... ).

Trailing zeros in n! ka relation?

Trailing zeros = min(v_2(n!), v_5(n!)). Factorial me 2 zyada hota hai, so usually v_5(n!) hi answer hota hai.

14. Highest Power of a Prime in n! (Legendre’s Formula)

Legendre’s Formula se n! me kisi prime p ki highest power: v_p(n!) = ⌊n/p⌋ + ⌊n/p^2⌋ + ...; SSC CGL examples, highest power of a number in n!, practice questions with answers.

← Prev: Last Two Digits / Patterns Next: Trailing Zeros in n! →

1) Problem statement (SSC style)

“n! me prime p ki highest power kya hai?” ka matlab: n! me p kitni baar factor ke roop me aa raha hai. Isko v_p(n!) bolte hain (exponent of p in n!).

2) Legendre’s Formula (final formula)

v_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... (jab tak p^k ≤ n)

Hinglish intuition: 1..n me jitne numbers p se divisible hain, wo 1 p contribute karte hain (⌊n/p⌋). Jitne numbers p² se divisible hain, wo extra 1 p aur contribute karte hain (⌊n/p²⌋), and so on.

3) Example 1: Highest power of 2 in 10!

v₂(10!) = ⌊10/2⌋ + ⌊10/4⌋ + ⌊10/8⌋ + ⌊10/16⌋ = 5 + 2 + 1 + 0 = 8

So, 2⁸ divides 10! (but 2⁹ does not).

4) Example 2: Highest power of 5 in 100!

v₅(100!) = ⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24

5) Composite number power in n! (most asked)

Agar question ho: “n! is divisible by a^k, max k find” to method:

a ko prime factorization me tod do: a = p₁^e1 p₂^e2 ...
Har prime p ke liye v_p(n!) Legendre se nikalo.
Answer = min( ⌊v_p1(n!)/e1⌋, ⌊v_p2(n!)/e2⌋, ... )

Example 3: Highest power of 12 in 50!

12 = 2² × 3

v₂(50!) = ⌊50/2⌋+⌊50/4⌋+⌊50/8⌋+⌊50/16⌋+⌊50/32⌋ = 25+12+6+3+1 = 47
v₃(50!) = ⌊50/3⌋+⌊50/9⌋+⌊50/27⌋ = 16+5+1 = 22

12^k = 2^2k×3^k So k = min(⌊47/2⌋, ⌊22/1⌋) = min(23, 22) = 22

6) Quick links / uses

Trailing zeros in n! = min(v₂(n!), v₅(n!)) (usually v₅).
“n! divisible by p^k?” → check if v_p(n!) ≥ k.
“Largest k such that a^k divides n!” → composite method above.

7) Common traps

Formula me floor (⌊ ⌋) ignore mat karo.
Composite power me divide by exponent e (like 12 has 2^2).
Sum terms stop when p^k > n.

8) Practice (SSC CGL) + Answers

Find v₂(25!).
Find v₅(200!).
Highest power of 6 in 20!?
Highest power of 24 in 100!?
Is 2⁶⁰ a factor of 50!? (Yes/No)
Find v₃(100!).

Show Answers

v2(25!) = ⌊25/2⌋+⌊25/4⌋+⌊25/8⌋+⌊25/16⌋ = 12+6+3+1 = 22
v5(200!) = ⌊200/5⌋+⌊200/25⌋+⌊200/125⌋ = 40+8+1 = 49
6=2×3; v2(20!)=10+5+2+1=18, v3(20!)=6+2=8 ⇒ k=min(18,8)=8
24=2^3×3; v2(100!)=50+25+12+6+3+1=97, v3(100!)=33+11+3+1=48 ⇒ k=min(⌊97/3⌋=32, 48)=32
v2(50!)=25+12+6+3+1=47 ⇒ 47≥60? No ⇒ No
v3(100!) = ⌊100/3⌋+⌊100/9⌋+⌊100/27⌋+⌊100/81⌋ = 33+11+3+1 = 48

← Prev Next →