Legendre-kaava

In matematiikan ja tarkemmin sanoen useissa teoriassa , Legendren kaava - totesi Adrien-Marie Legendren - antaa lauseke, sillä mikä tahansa alkuluku p ja mikä tahansa luonnollinen luku n , ja p -adic arvostus on factorial on n (l 'eksponentti p on Alkutekijähajotelma on n !, tai jälleen, suurin kokonaisluku siten, että jakaa n !): v{\ displaystyle v}sv{\ displaystyle p ^ {vb}}

vs(ei!)=∑k=1∞⌊ei/sk⌋=⌊ei/s⌋+⌊ei/s2⌋+⋯{\ displaystyle v_ {p} (n!) = \ summa _ {k = 1} ^ {\ infty} \ lfloor n / p ^ {k} \ rfloor = \ lfloor n / p \ rfloor + \ lfloor n / p ^ {2} \ rfloor + \ cdots} jossa tarkoittaa kokonaisluku osa on myös huomattava . ⌊x⌋{\ displaystyle \ lfloor x \ rfloor}x{\ displaystyle x}E(x){\ displaystyle E (x)}

Tämä kaava vastaa vs(ei!)=ei-ss(ei)s-1{\ displaystyle v_ {p} (n!) = {\ frac {n-s_ {p} (n)} {p-1}}} jossa tarkoittaa summa numeroa on emästä . ss(ei){\ displaystyle s_ {p} (n)}ei{\ displaystyle n} s{\ displaystyle p}

Esimerkkejä käytöstä

• Ja kiinteä, tämä kaava osoittaa, että kartta on vähenemässä, toisin sanoen, että kaikki kertoman on tuote primorials .ei{\ displaystyle n}s↦vs(ei!){\ displaystyle p \ mapsto v_ {p} (n!)}
• Kuinka monta nollaa päät  (in) numero  ?  : numero päättyy siis nollilla.2016!{\ displaystyle 2016!}v10(2016!)=min(v2(2016!),v5(2016!))=v5(2016!)=⌊2016/5⌋+⌊2016/25⌋+⌊2016/125⌋+⌊2016/625⌋=403+80+16+3=502{\ displaystyle v_ {10} (2016!) = \ min (v_ {2} (2016!), v_ {5} (2016!)) = v_ {5} (2016!) = \ lfloor 2016/5 \ rfloor + \ lfloor 2016/25 \ rfloor + \ lfloor 2016/125 \ rfloor + \ lfloor 2016/625 \ rfloor = 403 + 80 + 16 + 3 = 502}502{\ displaystyle 502}
• Kokonaisluku tarkastuksia , jos ja vain jos on 2: n potenssi . Todellakin, on 2: n voima.ei>0{\ displaystyle n> 0}2ei-1∣ei!{\ displaystyle 2 ^ {n-1} \ n keskellä!}ei{\ displaystyle n}2ei-1∣ei!⇔v2(ei!)≥ei-1⇔ei-s2(ei)≥ei-1⇔s2(ei)≤1⇔ei{\ displaystyle 2 ^ {n-1} \ n keskellä! \ Vasenkätinen nuoli v_ {2} (n!) \ geq n-1 \ Vasen suora n-s_ {2} (n) \ geq n-1 \ Vasen suora s_ {2 } (n) \ leq 1 \ vasen nuoli n}
• Binomikertoimien ovat kokonaislukuja määritelmän. Osoitetaan se uudelleen lausekkeesta (for ). Voit tehdä tämän, vain tarkistaa, että jokainen alkuluku p , . Legendren kaavan ja ominaisuuden mukaan meillä on:(eim)=ei!m!(ei-m)!{\ displaystyle {n \ select m} = {\ frac {n!} {m! (nm)!}}}0≤m≤ei{\ displaystyle 0 \ leq m \ leq n}vs(m!)+vs((ei-m)!)≤vs(ei!){\ displaystyle v_ {p} (m!) + v_ {p} ((nm)!) \ leq v_ {p} (n!)}⌊x⌋+⌊y⌋≤⌊x+y⌋{\ displaystyle \ lfloor x \ rfloor + \ lfloor y \ rfloor \ leq \ lfloor x + y \ rfloor}

vs(m!)+vs((ei-m)!)=∑k=1∞(⌊m/sk⌋+⌊(ei-m)/sk⌋)≤∑k=1∞⌊m/sk+(ei-m)/sk⌋=∑k=1∞⌊ei/sk⌋=vs(ei!){\ displaystyle v_ {p} (m!) + v_ {p} ((nm)!) = \ summa _ {k = 1} ^ {\ infty} \ vasen (\ lfloor m / p ^ {k} \ rfloor + \ lfloor (nm) / p ^ {k} \ rfloor \ right) \ leq \ sum _ {k = 1} ^ {\ infty} \ lfloor m / p ^ {k} + (nm) / p ^ {k } \ rfloor = \ summa _ {k = 1} ^ {\ infty} \ lfloor n / p ^ {k} \ rfloor = v_ {p} (n!)}. (Jos haluat mennä pidemmälle, katso Kummerin lause binomikerroista .)

Esittelyt

Huomata ensimmäinen että k > log p ( n ) , . ⌊ei/sk⌋=0{\ displaystyle \ lfloor n / p ^ {k} \ rfloor = 0}

Kokonaisluvuista mihin asti (josta tuote on tulo ) numeroidaan kerrannaiset , joten ne, joiden p -adic- arvo on tarkalleen, numeroidaan . Siksi, 1{\ displaystyle 1}ei{\ displaystyle n}ei!{\ displaystyle n!}sk{\ displaystyle p ^ {k}}⌊ei/sk⌋{\ displaystyle \ lfloor n / p ^ {k} \ rfloor}k{\ displaystyle k}⌊ei/sk⌋-⌊ei/sk+1⌋{\ displaystyle \ lfloor n / p ^ {k} \ rfloor - \ lfloor n / p ^ {k + 1} \ rfloor}

vs(ei!)=(⌊ei/s⌋-⌊ei/s2⌋)+2(⌊ei/s2⌋-⌊ei/s3⌋)+3(⌊ei/s3⌋-⌊ei/s4⌋)+...{\ displaystyle v_ {p} (n!) = \ vasen (\ lfloor n / p \ rfloor - \ lfloor n / p ^ {2} \ rfloor \ right) +2 \ left (\ lfloor n / p ^ {2 } \ rfloor - \ lfloor n / p ^ {3} \ rfloor \ right) +3 \ left (\ lfloor n / p ^ {3} \ rfloor - \ lfloor n / p ^ {4} \ rfloor \ right) + \ pisteet},

joka antaa yksinkertaistamisen jälkeen ensimmäisen ilmoitetun tasa-arvon.

Osoita, että se vastaa toista, harkitsemalla emäksen hajoamista  : (jossa arvo j > log p ( n ) ). Niin, ei{\ displaystyle n}s{\ displaystyle p}ei=∑j=0∞eijsj{\ displaystyle n = \ summa _ {j = 0} ^ {\ infty} n_ {j} p ^ {j}}eij=0{\ displaystyle n_ {j} = 0}

∑k≥1⌊ei/sk⌋=∑k≥1∑j≥keijsj-k=∑j≥1eij∑1≤k≤jsj-k=∑j≥1eijsj-1s-1=1s-1(∑j≥1eijsj-∑j≥1eij)=(ei-ei0)-(ss(ei)-ei0)s-1=ei-ss(ei)s-1{\ displaystyle \ summa _ {k \ geq 1} \ lfloor n / p ^ {k} \ rfloor = \ summa _ {k \ geq 1} \ summa _ {j \ geq k} n_ {j} p ^ {jk } = \ summa _ {j \ geq 1} n_ {j} \ summa _ {1 \ leq k \ leq j} p ^ {jk} = \ summa _ {j \ geq 1} n_ {j} {\ frac { p ^ {j} -1} {p-1}} = {\ frac {1} {p-1}} \ vasen (\ summa _ {j \ geq 1} n_ {j} p ^ {j} - \ summa _ {j \ geq 1} n_ {j} \ oikea) = {\ frac {(n-n_ {0}) - (s_ {p} (n) -n_ {0})} {p-1}} = {\ frac {n-s_ {p} (n)} {p-1}}}.

Katso myös

Aiheeseen liittyvä artikkeli

P-adic-eksponentiaalifunktio  (in) (Legendren kaavasta seuraa, että sen lähentymissäde on ) s-1/(s-1){\ displaystyle p ^ {- 1 / (p-1)}}

Ulkoinen linkki

Pierre Bornsztein et ai. , Aritmeettinen kurssi valmisteltaessa International matematiikkaolympialaiset , s. 12-14, 25-26, 32 ja 105

Bibliografia

Mohammed Aassila, 400 korjattua algebraharjoitusta kurssimuistutuksilla , Pariisi, Ellipsit , 2013 ( ISBN  978-2729881733 )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">