Matematické Fórum

FliegenderZirkus · 26. 08. 2009 21:03

Nepovedlo se mi ukázat, že $80 \mid (19^{99}-99^{19})$ , úloha pochází z mého oblíbeného zdroje, konkrétně z roku 1999. Je mi akorát jasné, že jakožto rozdíl dvou lichých čísel musí být výraz vpravo sudý, ale ještě zbývá ta dělitelnost 40...
Jsou to vlastně přijímačky na VŠ, docela mě znepokojuje, kolik z toho nedokážu spočítat...poradíte?

Pavel Brožek · 26. 08. 2009 23:14

Je dobré si rozepsat:
19=20-1
99=100-1

Pomůže to?

Olin · 26. 08. 2009 23:26 — Editoval Olin (26. 08. 2009 23:27)

Já si to nejprve upravil:

$19^{99}-99^{19} \equiv 99^{99}-99^{19} (\mathrm{mod}\, 80)\nl 99^{99}-99^{19} = 99^{19}(99^{80}-1)$

Výraz v závorce můžeme několikrát rozložit a z toho vyvodit patřičné závěry…

Kondr · 27. 08. 2009 09:39

$99^{19}-19^{99}\equiv -1^{19}-(-1)^{99}\equiv -1-(-1)\equiv 0\pmod{5}$
$99^{19}-19^{99}\equiv 19^{19}-19^{99}\equiv 19^{19}-19^{19}\equiv 0\pmod{16}$ , předposlední krok využívá Eulerovu větu.

FliegenderZirkus · 27. 08. 2009 20:54

Chvíli mi to trvalo, ale už do toho asi vidím, z té Eulerovy věty plyne, že
$19^{\varphi(16)}\equiv1 (\mathrm{mod}\, 16)$
$19^{8}\equiv1 (\mathrm{mod}\, 16)$ , takže od začátku to bude
$19^{99}-99^{19}\equiv19^{99}-(99-80)^{19}\equiv19^{80}\cdot19^{19}-19^{19}\equiv(19^8)^{10}\cdot19^{19}-19^{19}\equiv1^{10}\cdot19^{19}-19^{19}\equiv0 (\mathrm{mod}\, 16)$
A ta dělitelnost pěti:
$19^{99}-99^{19}\equiv(19-4\cdot5)^{99}-(99-20\cdot5)^{19}\equiv0 (\mathrm{mod}\, 5)$
Chápu to správně? Dík

Kondr · 27. 08. 2009 23:23

↑ FliegenderZirkus:Přesně tak. Ono když s kongruencemi chvíli počítáš, tak to jsou takové automatické úpravy: snížit/zvýšit základ o násobek modulu, snížit/zvýšit exponent o násobek $\phi(modulu)$ , třeba na MO to myslím není potřeba rozepisovat tak podrobně, jak jsi uvedl.

Olin · 28. 08. 2009 00:19

↑ Kondr:
Hned jsem si říkal, že to půjde nějak snadno a rychle přes Eulera. Bohužel s ním neumím tak obratně zacházet, tedy vždycky jsem to chvíli uměl, ale pak jsem to zase rychle zapomněl.

FliegenderZirkus · 28. 08. 2009 10:51

Jasně, já jsem jenom ještě s kongruencemi nikdy nepočítal, tak jsem si to chtěl ujasnit. Díky

check_drummer · 12. 09. 2009 00:24

Ahoj,
vzhledem k tomu, že u zadání úlohy je uvedeno, že slouží jako přijímačky na VŠ, tedy by asi bylo možné ji vyřešit pouze se základními středoškolskými znalostmi. Pokusme se o to - z netriviálních znalostí nám bude stačit jen binomická věta. (Výrazy c1, c2, ... budu označovat nějaký složitější výraz, který je celým číslem, který je relativně složitý, avšak na jehož přesném tvaru nezáleží.) Ještě k této poznámce kolegy: "Je mi akorát jasné, že jakožto rozdíl dvou lichých čísel musí být výraz vpravo sudý, ale ještě zbývá ta dělitelnost 40..." Tato úvaha není správná, protože pokud by se podařilo dokázat dělitelnost 40, nevíme nic o dělitelnosti 80 (díky tomu, že NSD 40 a 2 není 1).

Předně je dobré si uvědomit, že lichá mocnina čísla, které končí 9, končí také 9 a rozdíl dvou čísel s touto vlastností končí na 0 - tedy je toto číslo dělitelné 10 (a tedy i 5). Zbývá ověřit dělitelnost 16:

$19^{99}-99^{19} = 19^{99}-(19 + 80)^{19} = 19^{99}-19^{19} + 80c_1 = 19^{19}(19^{80}-1) + 80c_1$
Jelikož 16 nedělí mocninu 19, bude výraz dělitelný 16 právě když $16 \mid (19^{80}-1)$
$19^{80}-1 = (16+3)^{80}-1 = 3^{80}-1 + 16c_2 = (1+2)^{80}-1 + 16c_2 = {80 \choose 1}2^1 + {80 \choose 2}2^2 + {80 \choose 3}2^3 + 16c_3$

Ovšem zřejmě $80 \mid {80 \choose 1}2^1 + {80 \choose 2}2^2 + {80 \choose 3}2^3$ , čímž je důkaz proveden.

Pavel Brožek · 12. 09. 2009 12:39

Jen abych dokončil svůj návrh řešení (použiju stejné značení nezajímavých čísel jako ↑ check_drummer:):

$19^{99}-99^{19}=(20-1)^{99}-(100-1)^{19}=\nl =\[20^2\cdot c_1+{99\choose1}\cdot20\cdot(-1)^{98}+(-1)^{99}\]-\[100^2\cdot c_2+{19\choose1}\cdot100\cdot(-1)^{18}+(-1)^{19}\]=\nl =\[400\cdot c_1+1980-1\]-\[10000\cdot c_2+1900-1\]=80\cdot(5c_1-125c_2)+80=80c_3$

Matematické Fórum

#1 26. 08. 2009 21:03

Dělitelnost 80

#2 26. 08. 2009 23:14

Re: Dělitelnost 80

#3 26. 08. 2009 23:26 — Editoval Olin (26. 08. 2009 23:27)

Re: Dělitelnost 80

#4 27. 08. 2009 09:39

Re: Dělitelnost 80

#5 27. 08. 2009 20:54

Re: Dělitelnost 80

#6 27. 08. 2009 23:23

Re: Dělitelnost 80

#7 28. 08. 2009 00:19

Re: Dělitelnost 80

#8 28. 08. 2009 10:51

Re: Dělitelnost 80

#9 12. 09. 2009 00:24

Re: Dělitelnost 80

#10 12. 09. 2009 12:39

Re: Dělitelnost 80

Zápatí