큰 거듭제곱수의 일의자리수 구하기

2^4를 계산하면 16. 일의자리는 6.
3^5를 계산하면 243. 일의자리는 3.

하지만 4^26 와 같은 수는?
계산하면 4503599627370496. 일의자리는 6.

지수가 조금만 커져도 거듭제곱연산의 결과는 매우 커진다.
때문에 구하려고하는 일의자리수도 구하기에 부담이된다.

여기서 나머지(모듈러)연산을 이용하면 쉽게 구할 수 있다.

주기 찾기

7을 예시로 들어보자.

7^1 = 일의자리는 7
7^2 = 일의자리는 9
7^3 = 일의자리는 3
7^4 = 일의자리는 1
7^5 = 일의자리는 7
7^6 = 일의자리는 9
7^7 = 일의자리는 3
7^8 = 일의자리는 1
7^9 = 일의자리는 7
...

7,9,3,1이 반복되는게 보인다.
이때 주기는 4이다. (4번씩 반복하니깐~)
그리고 이 뜻은 일의자리 숫자는 무조건 7,9,3,1 중에서 나온다는걸 의미한다.

그렇담 이제 7^32 값의 일의자리수는 몇일까? (마찬가지로 7,9,3,1 중에 하나일 것이다.)

나머지연산

아까의 주기찾기로 잠시 돌아가서,
7^1 = 일의자리는 7
7^2 = 일의자리는 9
7^3 = 일의자리는 3
7^4 = 일의자리는 1 일때,

각 지수를 주기인 4로 나머지연산을 해보면 다음과 같다.

이때, N으로 나머지연산을하면 결과는 0~N-1 만 나오게 된다.

1 % 4 = 1
2 % 4 = 2
3 % 4 = 3
4 % 4 = 0

나머지연산을 함으로써 지수가 각 index에 대응되는걸 볼 수 있다.

이제 나머지연산한 결과와 반복되는 값을 대응해보면 다음과 같다.

7^32 ?

지수인 32를 7의 반복주기인 4로 나머지연산을 해보자.
32 % 4 = 0

위에서 그린 표의 0과 대응되는 결과는 1 이므로

7^32 의 일의자리숫자는 '1' 이다.

마치며

나머지연산을 하게되면 주기(패턴)을 찾게되어
크게 반복해야 할 일이 있다면, 나머지값만으로도
원하는 값을 쉽게 얻을 수 있다.