Bästa svaret
Först måste du titta på modulen (eller nummer som vi försöker dela med). I det här fallet är det 1818. Sedan infogar du 1818 i Eulers totientfunktion för att få ϕ (18) ϕ (18). För alla heltal nn har vi
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
där produkten går över alla unika huvudfaktorer för nn. Så i det här fallet,
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, så nästa steg är Eulers teorem , som säger att för alla andra heltal aa som är relativt primär till nn, vi har att aa till ϕ (n) ϕ (n) kraften lämnar en återstod på 11 när dividerat med nn. Det vill säga
aϕ (n) ≡1 (modn). Aϕ (n) ≡1 (modn).
Eftersom 1717 verkligen är relativt primärt till 1818 vet vi 176176 löv en påminnelse om 1. Detta innebär att vi bara kan fortsätta dela 176176 av 1720017200 utan att ändra resten. Ett annat sätt att säga detta är att 17 till vilken kraft som ”en multipel av 6 kommer att lämna en återstod på 1. Så till slut, eftersom 200 är 2 mer än en multipel av 6, vet vi att
17200≡172 (mod18) .17200≡172 (mod18).
Detta gör problemet mycket enklare – vi är nästan där! En genväg här för att avsluta problemet är att inse att 1717 lämnar en återstod av −1−1 dividerat med 1818 (dvs. 17≡ − 1 (mod18) 17≡ − 1 (mod18)), så 172172 lämnar en återstod av (- 1) 2 = 1. (- 1) 2 = 1.
Så vårt svar är 1 . Nästa gång du har problem med resten med stor kraft kan du använda den här fina generaliserade lösningen och låta smart samtidigt :). Om du inte har sett modmod-notationen tidigare, se Modular aritmetic .
PS Du kanske har hört talas om ett speciellt fall av denna teorem kallas Fermat ”s lilla sats , som fungerar när du har en modul som” är ett primtal (inte fallet här). Satsen säger att för alla primtal pp och heltal aa som inte är en multipel av pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Detta är ett intressant trick men dess i princip samma som vad som står ovan eftersom ϕ (p) = p − 1ϕ (p) = p − 1 för alla primära sidor. Denna typ av frågor blir riktigt enkla om du förstår begreppet negativa rester . Försök alltid att sänka utdelningen till 1 eller -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Svar
Viktig bakgrund som behövs för att lösa problemet :
Vi vet att resten erhålls när r delar pq är en produkt av återstoder som erhålls när r delar p och qseparat. Detta kallas lemma för resten. Du kan bevisa det med Euclids divisionssats.
Lösningen
17 när den delas med 18 kvar resten -1 (det är bekvämt att arbeta med -1 än 17)
Att tillämpa återstående lemma på 17 × 17 × 17 … × 17 (2000 gånger) dividerat med 18 kommer att erhållas när enskilda rester multipliceras dvs -1 × -1 .. × -1 (2000 gånger) som är återstoden är 1 \ svart kvadrat
Om den var 17 höjd till något udda tal skulle resten vara -1 eller 17 .