Paras vastaus
Ensinnäkin meidän on tarkasteltava moduulia (tai numero, jota yritämme jakaa). Tässä tapauksessa se on 1818. Sitten lisätään 1818 Euler -funktioon saadaksesi ϕ (18) ϕ (18) .Ennen kaikkia kokonaislukuja nn, meillä on
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
missä tuote kulkee kaikkien nn ainutlaatuisten alkutekijöiden läpi. Joten tässä tapauksessa
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, joten seuraava vaihe on Eulerin lause , joka sanoo, että muille kokonaisluvuille aa, jotka ovat suhteellisen prime arvoon nn, meillä on, että aa ϕ (n) ϕ (n) -teholle jättää loput 11, kun se jaetaan nn: llä. Toisin sanoen
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Koska 1717 on todellakin suhteellisen alkeellinen vuoteen 1818, tiedämme 176176 lehteä muistutus 1. Tämä tarkoittaa, että voimme vain jakaa 176176 1720017200: sta muuttamatta loppuosaa. Toinen tapa sanoa tämä on se, että 17 mihin tahansa voimaan, joka ”on 6: n moninkertainen, jättää loput 1: stä. Joten lopulta, koska 200 on 2 enemmän kuin 6: n moninkertainen, tiedämme, että
17200≡172 (mod18). 17200≡172 (mod18).
Tämä tekee ongelmasta paljon yksinkertaisemman – olemme melkein siellä! Pikanäppäin ongelman loppuun saattamiseksi on ymmärtää, että 1717 jättää lopun −1−1, kun se jaetaan 1818: lla (ts. 17≡ − 1 (mod18) 17≡ − 1 (mod18)), joten 172172 jättää loput (- 1) 2 = 1. (- 1) 2 = 1.
Joten vastauksemme on 1 . Seuraavalla kerralla sinulla on ongelmia loput suuritehoisena voit käyttää tätä mukavaa yleistettyä ratkaisua ja kuulostaa älykkäältä samanaikaisesti :). Jos et ole vielä nähnyt modmod-merkintää, katso Modulaarinen aritmeettinen .
PS Olet ehkä kuullut tämän lauseen erikoistapauksesta nimeltään Fermatin pieni lause , joka toimii, kun moduuli on alkuluku (ei tässä tapauksessa). Lause sanoo, että minkä tahansa alkupp: n kohdalla ja kokonaisluku aa, joka ei ole pp: n moninkertainen,
ap − 1≡1 (modp). ap − 1≡1 (modp).
Tämä on mielenkiintoinen temppu, mutta sen pohjimmiltaan sama kuin mitä ”s edellä, koska ϕ (p) = p − 1ϕ (p) = p − 1 mille tahansa prime pp: lle. Tämän tyyppiset kysymykset muuttuvat todella yksinkertaisiksi, jos ymmärrät negatiiviset jäännökset . Yritä aina ja pienennä osinko arvoon 1 tai -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Vastaa
Tärkeä tausta ongelman ratkaisemiseksi :
Tiedämme, että loppuosa, joka saadaan, kun r jakaa pq, on lopputuotteiden tulos, joka saadaan, kun r jakaa p ja q erikseen. Tätä kutsutaan lemmaksi jäännöksissä. Voit todistaa sen Euclidin jakolauseella.
Ratkaisu
17 jaettuna 18: lla jättää loput -1 (on kätevää työskennellä -1: n kuin 17: n kanssa)
Jäljelle jäävän lemman soveltaminen arvoon 17 × 17 × 17 … × 17 (2000 kertaa) jaettuna 18: lla saadaan loppuosa, kun yksittäiset jäännökset kerrotaan eli -1 × -1 .. × -1 (2000 kertaa), eli loppuosa on 1 \ mustan neliön
Jos se korotettaisiin 17 parittomaan lukuun, loput olisivat -1 tai 17 .