2010²²÷7의 나머지를 구하라
기출문제를 풀다보면 위 문제와 같이 숫자가 큰 값의 나머지 구하기문제를 종종 볼 수 있을 텐데
많은 수험생이 곤혹을 치르는 문제이다. 많은 책에서 설명조차 안하는 부분이기 때문이다.
따라서 개인적으로 푸는 방법을 소개하려 한다.
이 방법은 책을 봐서 얻은 지식이 아닌, 내가 직접 머리를 굴리다가 찾아낸 방법이다.
설명을 하기 위해 예를 들어보자.
10을 7로 나눈 나머지는 3이다.
100을 7로 나눈 나머지는 2이다.
1000을 7로 나눈 나머지는 6이다.
10000을 7로 나눈 나머지는 4이다.
자 그렇다면 무엇인가를 유추해보자.
10을 7로 나눈 나머지는 3이고
10²을 7로 나눈 나머지는 2이다.
10²을 7로 나눈 나머지를 구하는 방법은
10을 7로 나누었을 때 나머지를 제곱한 후 다시 7로 나누었을 때의 나머지와 같다.
즉, 10을 7로 나눈 나머지가 3이므로 10²을 7로 나눈 나머지는 3² ÷7 , 2가 된다.
그렇다면 10³을 7로 나눈 나머지는 어떻게 될까?
마찬가지로 풀어준다. 10을 7로 나눈 나머지를 구한 후 그 나머지의 세제곱을 한 값을 7로 나누어준다.
즉, 10을 7로 나눈 나머지가 3이므로 10³을 7로 나눈 나머지는 3³÷7, 6이 된다.
그렇다면 제일 처음에 있는 2010²²÷7의 나머지를 구해보자.
2010²²을 7로 나눈 나머지를 알기위해 우선 2010을 7로 나눈 나머지의 값을 알아야 한다.
2010을 7로 나눈 나머지는 1이 되므로 2010²을 7로 나눈 나머지도 1, 2010³을 7로 나눈 나머지도 1 .....
즉 2010²²을 7로 나눈 나머지는 1이 된다. 실제로 계산해 보아도 나머지는 계속 1이 나온다.
47³¹을 3으로 나눈 나머지는 어떻게 될까?
47을 3으로 나누면 나머지는 2
47²을 3으로 나누면 나머지는 1
47³을 3으로 나누면 나머지는 2
47⁴을 3으로 나누면 나머지는 1
.
.
.
지수가 홀수이면 2, 짝수이면 1이라는 규칙이 나오게 된다.
따라서 47³¹을 3으로 나누면 나머지는 2가 된다.
이렇듯 나머지값은 주기적으로 순환하게 된다.
그리고 또 한가지 알려주자면
나누려는 값을 먼저 연산한 값을 나누어 준 나머지와 나누려는 값을 먼저 나눈 나머지끼리의 연산과 같다.
이것도 예를 들어보자.
2009² X 2010³ + 2000²을 7로 나눈 나머지를 구하라는 문제가 있다고 해보자.
이 경우 2009² X 2010³ = 16306170848100 + 4000000 = 1630657084100을 7로 나눈 나머지를 구하는 값과
2009²을 7로 나눈 나머지 0
2010³을 7로 나눈 나머지 1
2000²을 7로 나눈 나머지 4
나머지끼리 연산 즉, 0 X 1 + 4 = 4의 값은 같다.
자, 그렇다면 마지막으로 문제 하나만 풀어보자. 작년 고려대학교 기출문제이다.
37^49 을 7로 나눈 나머지는?