거듭제곱의 나머지

ㄱ. $2 ^{4} + 1 = 17$을 3으로 나눈 나머지는 2이므로 $f ( 4 ) = 2$ (참) ㄴ. n이 홀수이면 $n = 2 k + 1$ (k는 음이 아닌 정수)로 놓을 수 있다. $2 ^{n} + 1 = 2 ^{2k+1} + 1 = 2 ^{2k} \cdot 2 + 1$ $= 2 \cdot 4 ^{k} + 1 = 2 \cdot 4 ^{k} - 2 + 2 + 1$ $= 2 ( 4 ^{k} - 1 ) + 3$ 여기에서 $4 ^{k} - 1$은 $k = 0$일 때 $0$이고, $k \geq 1$일 때 $4 ^{k} - 1 = ( 2 ^{k} - 1 ) ( 2 ^{k} + 1 )$이므로 3의 배수이다. ($\because k = 1 , 2 , 3 , \cdots$일 때, $2 ^{k} - 1$ 또는 $2 ^{k} + 1$이 3의 배수이다.) 즉, $4 ^{k} - 1$이 $3$의 배수이므로 $2 ( 4 ^{k} - 1 ) + 3$도 3의 배수가 되어 n이 홀수이면 $2 ^{n} + 1$은 $3$으로 나누어 떨어진다. 따라서, n이 홀수이면 $f ( n ) = 0$이다. (참) ㄷ. n이 짝수이면 n=2k (k 는 양의 정수)로 놓을 수 있다. $2 ^{n} + 1 = 2 ^{2k} + 1$$= 4 ^{k} - 1 + 1 + 1$$= ( 4 ^{k} - 1 ) + 2$ ㄴ에서 k가 양의 정수일 때 $4 ^{k} - 1$은 3의 배수이므로 $( 4 ^{k} - 1 ) + 2$를 3으로 나누면 나머지는 2이다. 즉, $2 ^{n} + 1$을 3으로 나누면 나머지가 2이므로 n이 짝수이면 $f ( n ) = 2$이다. ∴ $f ( f ( n ) ) = f ( 2 ) = 2$ ($\because 2$는 짝수) (참)