나머지정리 응용예제42 풀이

\(2^{29}\)을 17로 나눈 나머지는?

해설: 이런 문제를 출제해야 하는지 의문입니다. 그냥 다항식 문제를 내는 것이 바람직해 보입니다.

주어진 숫자를 이렇게 생각해 보십시오:

\(2^{29}=2^4 \times 2^4 \times \cdots\)

\(2^4=16\)이라는 숫자는 17로 나누었을 때, 그 자체가 나머지이지만, 다르게는 \(-1\)이라는 숫자로 생각할 수 있습니다. 즉, 17로 나눈 나머지가 \(-1\)이라는 것은 나머지가 16이라는 것과 동치입니다.

따라서, \(2^4\times 2^4 = 2^8\)이고, 17로 나눈 나머지는 \((-1) \times (-1) = 1\)이고, 8개씩 묶어서 나머지 1을 만들어 내므로, \(2^{29}\)을 17로 나눈 나머지는 \(2^{5}\)을 17로 나눈 나머지와 같습니다.

이제, \(2^5=2^4 \times 2\)을 17로 나눈 나머지는 이전 논리에 의해 \(-2\)임을 알 수 있고, 나머지는 17을 더해서 15입니다. 

다른 경우로써, 13으로 나눈 나머지는 어떻게 구할까요?

여러 방법이 있겠지만, \(2^{29}=2^3 \times 2^3 \times 2^3 \times 2^3 \cdots\)이런 식으로 생각하면, \(2^{3}\)은 13으로 나누었을 때, 나머지가 자체이고, 다른 숫자로는 \(-5\)로 쓸 수 있고, \((-5) \times (-5)=25\)이고, 이것을 13으로 나누면 나머지가 12이지만, 다른 숫자로는 \(-1\)로 표현할 수 있습니다. 

즉, \(2^{3} \times 2^3 \times 2^3 \times 2^3 = 2^{12}\)는 13으로 나누면 나머지가 1이 되고, \(2^{29}\)을 13으로 나눈 나머지는 \(2^{5}\)을 13으로 나눈 나머지와 같습니다.

다른 응용) \(2^{290}\)을 17로 나눈 나머지는?

이런 경우에서, \(2^{290}= ({2^{29}})^{10}\)는 앞의 지식을 활용해서 \((-2)^{10}=2^{10}=2^8 \times 2^2 \equiv 4\)임을 알 수 있습니다.