Introduction
Number Theory और combinatorics में कई problems पूछती हैं: n! को divide करने वाला किसी prime का सबसे बड़ा power कितना है? यह trailing zeros निकालने, divisibility समझने और factorial-based expressions को simplify करने में useful होता है।
ऐसे problems को solve करने के लिए इस्तेमाल होता है Legendre’s Formula, जो बताता है कि n! को किसी prime से कितनी बार divide किया जा सकता है।
Pattern: Highest Power of a Prime in n!
Pattern
Legendre’s Formula prime p का exponent n! में इस तरह देती है:
vₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
Sum तब तक चलता है जब तक pᵏ > n न हो जाए। Result बताता है कि p का highest power जो n! को exactly divide करता है, कितना है। यानी p^vₚ(n!) n! को divide करता है, लेकिन p^(vₚ(n!)+1) divide नहीं करेगा।
- Use Cases: Trailing zeros निकालना (p = 5 लें), divisibility check करना, factorial ratios simplify करना।
- Intuition: p के हर multiple में एक p होता है, p² के multiples extra p देते हैं, और इसी तरह आगे।
Step-by-Step Example
Question
100! को divide करने वाला 2 का सबसे बड़ा power निकालें।
Solution
-
Step 1: Legendre’s Formula apply करें:
v₂(100!) = ⌊100/2⌋ + ⌊100/4⌋ + ⌊100/8⌋ + ⌊100/16⌋ + ⌊100/32⌋ + ⌊100/64⌋ + …
-
Step 2: हर term calculate करें:
⌊100/2⌋ = 50
⌊100/4⌋ = 25
⌊100/8⌋ = 12
⌊100/16⌋ = 6
⌊100/32⌋ = 3
⌊100/64⌋ = 1
⌊100/128⌋ = 0 (यहां रुकें) -
Step 3: सबको add करें:
v₂(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97
-
Final Answer:
100! को divide करने वाला 2 का highest power है 2⁹⁷ (exponent e = 97)।
-
Quick Check:
Trailing zeros के लिए हम 2 और 5 की powers compare करते हैं। v₅(100!) = ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24. क्योंकि 5 की तुलना में 2 ज्यादा होते हैं, trailing zeros = 24 ✅
Quick Variations
1. Highest power of 5 in n!: Trailing zeros के लिए उपयोग → v₅(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
2. Highest power of p in (n choose r): Formula: vₚ(C(n, r)) = vₚ(n!) - vₚ(r!) - vₚ((n-r)!).
3. जब pᵏ > n हो जाए, terms add करना बंद कर दें क्योंकि आगे contributions नहीं मिलेंगे।
Trick to Always Use
- Step 1: Legendre’s Formula apply करें - n को p, p², p³… से divide करते जाएँ और integer parts को add करें।
- Step 2: Trailing zeros निकालने के लिए हमेशा p = 5 लें क्योंकि 2s ज्यादा होते हैं।
- Step 3: Combination problems के लिए factorial exponents का difference लें।
- Step 4: Division result 0 होते ही रुक जाएँ - आगे कोई contribution नहीं मिलेगा।
Summary
Summary
- Legendre’s Formula से prime p का exponent n! में repeated division से निकाला जाता है - p, p², p³…
- जब division result 0 हो जाए, आगे terms जोड़ने की जरूरत नहीं।
- निकला हुआ exponent vₚ(n!) बताता है कि p का highest power exactly n! को divide करता है।
- Trailing zeros (p = 5), factorial divisibility और combination exponent problems में यह method बहुत useful है।
याद रखने वाला example:
v₂(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97 → highest power = 2⁹⁷.
Hint: Sum ⌊n/2⌋ + ⌊n/4⌋ + ⌊n/8⌋ … until terms are 0.
Common Mistakes: Forgetting to include higher powers like 16 and 32 which still contribute.