최상의 답변
언제나 몇 개의 작은 지수를 계산하고 나머지에 대한 반복 패턴을 찾을 수 있습니다. . n = 1부터 시작하여 2 ^ n의 나머지를 18로 나눈 값을 계산해 보겠습니다.
- n = 1, 2 ^ 1 = 2, 나머지는 2입니다.
- n = 2, 2 ^ 2 = 4, 나머지는 4입니다.
- n = 3, 2 ^ 3 = 8, 나머지는 8입니다.
- n = 4, 2 ^ 4 = 16 , 나머지는 16,
- n = 5, 2 ^ 5 = 32, 나머지는 14입니다.
- n = 6, 2 ^ 6 = 64, 나머지는 10입니다.
- n = 7, 2 ^ 7 = 128, 나머지는 2;
- n = 8, 2 ^ 8 = 256, 나머지는 4;
- \ cdots \ cdots
사실 지수가 커지면 실제 2의 거듭 제곱을 계산할 필요가 없습니다. 대신 이전 나머지에 2를 곱한 다음 해당 결과에서 새 나머지를 찾습니다. 나머지는 6 개의 숫자마다 반복된다는 것이 분명합니다. 따라서 지수 200의 경우 200을 6으로 나눈 나머지, 즉 2를 알아냅니다. 따라서 2 ^ {200}을 18로 나눈 나머지는 2 ^ 2의 나머지와 동일합니다. 4.
답변
2 ^ 4 \ equiv -2 \ pmod {18}
\ implies (2 ^ 4) ^ 5 \ equiv (-2 ) ^ 5 \ pmod {18}
\ implies (2 ^ 4) ^ 5 \ equiv -32 \ pmod {18}
\ implies 2 ^ {20} \ equiv 4 \ pmod {18}
\ implies (2 ^ {20}) ^ 5 \ equiv 4 ^ 5 \ pmod {18}
\ implies (2 ^ {100}) \ equiv 1024 \ pmod {18}
\ implies (2 ^ {100}) \ equiv -2 \ pmod {18}
\ implies (2 ^ {200}) \ equiv (-2) ^ 2 \ pmod {18}
\ implies (2 ^ {200}) \ equiv 4 \ pmod {18}
\ text {따라서 4가 나머지입니다. when} \, 2 ^ {200} \, \ text {를 18}로 나누었습니다.