Nejlepší odpověď
Nejprve se musíme podívat na modul (nebo číslo, které se pokoušíme rozdělit). V tomto případě je to číslo 1818. Potom vložíte znak 1818 do Eulerovy totientové funkce , abyste získali ϕ (18) ϕ (18). Zejména pro všechna celá čísla nn máme
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
kde produkt prochází všemi jedinečnými primárními faktory nn. V tomto případě tedy
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Dobře, takže dalším krokem je Eulerova věta , která říká, že pro jakékoli jiné celé číslo aa, které je relativně prime na nn, máme, že aa k moci ϕ (n) ϕ (n) ponechává zbytek 11, když je děleno nn. To znamená,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Jelikož rok 1717 je skutečně relativně vrcholný k roku 1818, známe 176176 listů připomínka 1. To znamená, že můžeme jednoduše rozdělit 176176 z 1720017200 beze změny zbytku. Jiným způsobem, jak to říci, je to, že 17 na jakoukoli mocninu, která „je násobkem 6, ponechá zbytek 1. Takže nakonec, protože 200 je 2 více než násobek 6, víme to
17200≡172 (mod18). 17200≡172 (mod18).
Tím je problém mnohem jednodušší – jsme téměř tam! Klávesovou zkratkou k dokončení problému je uvědomit si, že 1717 zanechává zbytek −1−1 po rozdělení 1818 (tj. 17≡ − 1 (mod18) 17≡ − 1 (mod18)), takže 172172 zanechává zbytek (- 1) 2 = 1. (- 1) 2 = 1.
Takže naše odpověď je 1 . Příště budete mít problém se zbytkem o velké síle, můžete použít toto pěkné zobecněné řešení a současně znít chytře :). Pokud jste modmodovou notaci ještě neviděli, přečtěte si část Modulární aritmetika .
PS Možná jste slyšeli o zvláštním případě této věty nazývá se Fermatova malá věta , která funguje, když máte modul, který je prvočíslem (v tomto případě neplatí). Věta říká, že pro všechny primární pp a celé číslo aa, které není násobkem pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Toto je zajímavý trik, ale jeho v zásadě stejné jako to, co je výše, protože ϕ (p) = p − 1ϕ (p) = p − 1 pro libovolné primární pp. Tyto otázky se stávají opravdu jednoduchými, pokud rozumíte konceptu negativní zbytky . Vždy se snažte snížit dividendu na 1 nebo -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Odpověď
Důležité pozadí potřebné k vyřešení problému :
Víme, že zbytek získaný, když r rozdělí pq, je produktem zbytků získaných, když r rozdělí p a q odděleně. Tomu se říká lemma na zbytcích. Dokážete to pomocí Euclidovy věty o dělení.
Řešení
17, když se dělí 18 zbývajícími listy -1 (je vhodné pracovat s -1 než 17)
Uplatnění zbytkového lematu na 17 × 17 × 17 … × 17 (2000krát), když se vydělí 18, se zbytek získá, když jednotlivé zbytky se vynásobí, tj. -1 × -1 .. × -1 (2 000krát), což je zbytek 1 \ blacksquare
Pokud by bylo 17 zvýšeno na nějaké liché číslo, zbytek by byl -1 nebo 17 .