Legjobb válasz
Először meg kell vizsgálnunk a modulust (vagy a szám, amellyel megpróbálunk osztani). Ebben az esetben ez az 1818. Ezután be kell illesztenie 1818-at a Euler totient függvényébe , hogy get (18) ϕ (18). Különösen az összes nn egész számra
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
ahol a termék az nn összes egyedi elsődleges tényezőjén halad. Tehát ebben az esetben
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Rendben, tehát a következő lépés az Euler tétel , amely szerint minden más aa egész számra, amely viszonylag prím az nn-hez, megvan, hogy aa az ϕ (n) ϕ (n) hatványra megmarad 11-ről, amikor elosztjuk nn-vel. Vagyis
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Mivel 1717 valóban viszonylag elsődleges 1818-hoz képest, 176176 levelet ismerünk emlékeztető az 1.-re. Ez azt jelenti, hogy a 176176-ot csak fel tudjuk osztani 1720017200-ból, anélkül, hogy a maradékot megváltoztatnánk. Ennek másik módja az, hogy 17 minden olyan hatványra, amely “6-szorosának többszöröse, megmarad 1-ből. Tehát végül, mivel 200 2-gyel több, mint 6-szorosa, tudjuk, hogy
17200≡172 (mod18). 17200≡172 (mod18).
Ez sokkal egyszerűbbé teszi a problémát – már majdnem ott vagyunk! A probléma befejezéséhez ide kattintva felismerhetjük, hogy az 1717 1818-mal elosztva elhagyja a -1 -1 fennmaradó részét (azaz 17≡-1 (mod18) 17≡-1 (mod18)), így 172172 marad (- 1) 2 = 1. (- 1) 2 = 1.
Tehát a válaszunk 1 . Legközelebb a fennmaradó rész problémája merül fel nagy teljesítményű, használhatja ezt a szép általánosított megoldást, és egyszerre okosan hangzik :). Ha még nem látta a modmod jelölését, olvassa el a moduláris aritmetika című részt.
PS Lehet, hogy hallottál már ennek a tételnek egy speciális esetéről az úgynevezett Fermat kis tétel , amely akkor működik, ha van egy modulusod, amely “prímszám (itt nem ez a helyzet). A tétel azt mondja, hogy minden prím pp esetén és aa egész szám, amely nem a pp többszöröse,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Ez egy érdekes trükk, de alapvetően ugyanaz, mint ami fent van, mivel prime (p) = p − 1ϕ (p) = p − 1 bármelyik elsődleges pp esetén. Ezek a típusú kérdések igazán egyszerűvé válnak, ha megérti a negatív maradványok . Mindig próbáld csökkenteni az osztalékot 1-re vagy -1-re.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Válasz
Fontos háttér szükséges a probléma megoldásához :
Tudjuk, hogy a maradék, amelyet akkor kapunk, ha r osztja a pq-t, az a maradék szorzata, amelyet akkor kapunk, amikor r külön osztja a p-t és a q-t. Ezt a maradékokon lemmának hívják. Az Euclid osztódási tételével bizonyíthatja.
A megoldás
17, ha elosztjuk 18-tal, maradék marad. -1 (kényelmes, ha -1-nél 17-nél dolgozunk)
A maradék lemma alkalmazása 17 × 17 × 17 … × 17-re (2000-szer), ha elosztjuk 18-mal, a maradékot akkor kapjuk meg, amikor a az egyes maradványokat megszorozzuk, azaz -1 × -1 .. × -1 (2000-szeres), vagyis a maradék értéke 1 \ blacksquare
Ha 17-et valamilyen páratlan számra emeltek, akkor a maradék értéke -1 vagy 17 .