Bästa svaret
Du kan alltid försöka beräkna några mindre exponenter och hitta ett upprepande mönster för de återstående . Låt oss beräkna resten av 2 ^ n dividerat med 18, börjar med n = 1:
- n = 1, 2 ^ 1 = 2, resten är 2;
- n = 2, 2 ^ 2 = 4, resten är 4;
- n = 3, 2 ^ 3 = 8, resten är 8;
- n = 4, 2 ^ 4 = 16 , resten är 16;
- n = 5, 2 ^ 5 = 32, resten är 14;
- n = 6, 2 ^ 6 = 64, resten är 10;
- n = 7, 2 ^ 7 = 128, resten är 2;
- n = 8, 2 ^ 8 = 256, resten är 4;
- \ cdots \ cdots
Faktum är att när exponenterna blir större behöver du inte beräkna de verkliga krafterna på 2; istället multiplicerar du bara den föregående resten med 2 och hittar sedan den nya resten från det resultatet. Det är tydligt att återstoden upprepar vart sjätte nummer. Så för exponenten 200 får vi bara reda på resten när 200 divideras med 6, vilket är 2. Därför är resten när 2 ^ {200} divideras med 18 samma som resten för 2 ^ 2, vilket är lika med 4.
Svar
2 ^ 4 \ equiv -2 \ pmod {18}
\ innebär (2 ^ 4) ^ 5 \ equiv (-2 ) ^ 5 \ pmod {18}
\ innebär (2 ^ 4) ^ 5 \ equiv -32 \ pmod {18}
\ innebär 2 ^ {20} \ equiv 4 \ pmod {18}
\ innebär (2 ^ {20}) ^ 5 \ ekviv 4 ^ 5 \ pmod {18}
\ innebär (2 ^ {100}) \ equiv 1024 \ pmod {18}
\ implicerar (2 ^ {100}) \ equiv -2 \ pmod {18}
\ implicerar (2 ^ {200}) \ equiv (-2) ^ 2 \ pmod {18}
\ innebär (2 ^ {200}) \ equiv 4 \ pmod {18}
\ text {Därför är 4 återstoden när} \, 2 ^ {200} \, \ text {delas med 18}