Introduction
number theory மற்றும் combinatorics பிரச்சினைகளில் அடிக்கடி கேட்கப்படும் கேள்வி: n! ஐ வகுக்கும் ஒரு prime எண் p-ன் மிக உயர்ந்த power எது? இது trailing zeros கண்டறிதல், வகுபாடு பண்புகள், மற்றும் factorial-அடிப்படையிலான expressions-ஐ எளிமைப்படுத்த உதவுகிறது.
இவ்வகை பிரச்சினைகளைத் தீர்க்க பயன்படுத்தப்படும் கருவி Legendre’s Formula ஆகும்; இது n! இல் ஒரு prime எத்தனை முறை வகுக்கப்படுகிறது என்பதை எண்ணுகிறது.
Pattern: Highest Power of a Prime in n!
Pattern
Legendre’s Formula n! இல் prime p-ன் exponent-ஐ இவ்வாறு அளிக்கிறது:
vₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …
pᵏ > n ஆகும் வரை இந்த கூட்டம் தொடரும். கிடைக்கும் மதிப்பே n! ஐ வகுக்கும் p-ன் மிக உயர்ந்த power. அதாவது, p^vₚ(n!) n! ஐ வகுக்கும்; ஆனால் p^(vₚ(n!)+1) வகுக்காது.
- Use Cases: trailing zeros (p = 5 பயன்படுத்தவும்), வகுபாடு சரிபார்ப்பு, factorial விகிதங்களை எளிமைப்படுத்தல்.
- Intuition: p-ன் ஒவ்வொரு multiple-மும் ஒரு p-ஐ வழங்கும்; p²-ன் multiples கூடுதல் p-ஐ வழங்கும்; இதுபோல் தொடரும்.
Step-by-Step Example
Question
100! ஐ வகுக்கும் 2-ன் மிக உயர்ந்த power-ஐக் கண்டறியுங்கள்.
Solution
-
Step 1: Legendre’s Formula பயன்படுத்துதல்:
v₂(100!) = ⌊100/2⌋ + ⌊100/4⌋ + ⌊100/8⌋ + ⌊100/16⌋ + ⌊100/32⌋ + ⌊100/64⌋ + …
-
Step 2: ஒவ்வொரு term-ஐ கணக்கிடுதல்:
⌊100/2⌋ = 50
⌊100/4⌋ = 25
⌊100/8⌋ = 12
⌊100/16⌋ = 6
⌊100/32⌋ = 3
⌊100/64⌋ = 1
⌊100/128⌋ = 0 (இங்கு நிறுத்தவும்) -
Step 3: அனைத்தையும் கூட்டுதல்:
v₂(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97
-
Final Answer:
100! ஐ வகுக்கும் 2-ன் மிக உயர்ந்த power = 2⁹⁷ (exponent = 97).
-
Quick Check:
trailing zeros க்கு 2 மற்றும் 5 powers-ஐ ஒப்பிடுகிறோம். v₅(100!) = ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24. 2-கள் 5-களைவிட அதிகம் என்பதால், trailing zeros எண்ணிக்கை = 24 ✅
Quick Variations
1. n! இல் 5-ன் மிக உயர்ந்த power: trailing zeros க்கு பயன்படும் → v₅(n!) = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …
2. (n choose r) இல் p-ன் மிக உயர்ந்த power: vₚ(C(n, r)) = vₚ(n!) - vₚ(r!) - vₚ((n-r)!).
3. pᵏ > n ஆனவுடன் நிறுத்துங்கள்; அதற்குப் பிறகு எந்த contribution-மும் இல்லை.
Trick to Always Use
- Step 1: Legendre’s Formula பயன்படுத்துங்கள் - n ஐ p, p², p³, … ஆகப் பிரித்து, கிடைக்கும் முழு எண்களை கூட்டுங்கள்.
- Step 2: trailing zeros க்கு எப்போதும் p = 5 பயன்படுத்துங்கள்; 2-கள் அதிகம் இருக்கும்.
- Step 3: combinations பிரச்சினைகளில் factorial exponents-ன் வேறுபாடுகளை பயன்படுத்துங்கள்.
- Step 4: division முடிவு 0 ஆனவுடன் நிறுத்துங்கள் - அதன் பின் terms எதுவும் சேராது.
Summary
Summary
- Legendre’s Formula மூலம் n! இல் ஒரு prime p-ன் exponent-ஐ p, p², p³, … ஆக மீண்டும் மீண்டும் பிரித்து கண்டறியலாம்.
- division முடிவு 0 ஆனவுடன் நிறுத்துங்கள்; அதன் பின் terms பயனில்லை.
- கணக்கிடப்பட்ட vₚ(n!) என்பதே n! ஐ துல்லியமாக வகுக்கும் p-ன் மிக உயர்ந்த power.
- இந்த முறை trailing zeros (p = 5), factorial divisibility, மற்றும் combination exponent பிரச்சினைகளுக்கு மிகவும் அவசியம்.
நினைவில் கொள்ள வேண்டிய உதாரணம்:
v₂(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97 → மிக உயர்ந்த 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.