7.4 Powers of Congruences

합동식 [eqn: a==b(modm)]을 다시 보자.

제곱을 하면

[eqn: a^{ 2} ==b ^{ 2} (modm)].

일반적으로 양의 정수 [eqn: n]에 대하여

[eqn: a^{ n} ==b ^{ n} (modm)].

예를 들자.

[eqn: 8==-3(mod11)]

제곱을 하면

[eqn: 64==9(mod11)]

세제곱을 하면

[eqn: 512 ==-27(mod11)]

합동식 결과의 많은 것은 높은 지수의 수가 가지는 나머지를 찾는 것과 관련된다. 진행의 과정이 어떻게 되는지 나타내어보자.

예를 들어

[eqn: 3^{ 89}(mod7)]

을 찾아보자.

하나의 방법은 제곱을 반복하는 것이다.

[eqn: 9=3 ^{ 2} ==2(mod7)]

[eqn: 3^{ 4} ==4]

[eqn: 3^{ 8} ==16 ==2]

[eqn: 3^{ 16} ==4]

[eqn: 3^{ 32} ==16 ==2]

[eqn: 3^{ 64} ==4(mod7)]

[eqn: 89=64+16+8+1=2 ^{ 6}+2 ^{ 4}+2 ^{ 3}+1]이므로

[eqn: 3^{ 89}=3 ^{ 64} BULLET3 ^{ 16} BULLET3 ^{ 8} BULLET3 ==4 BULLET4 BULLET2 BULLET3 ==5(mod7)].

따라서 [eqn: 3^{ 89}(mod7)]은 5이다.: 다시 말하면 7.2절로부터 기저가 7인 [eqn: 3^{ 89}]의 마지막 숫자는 5이다.

나머지를 찾기 위해 지수인 89를 이진법 체계로 쓰면

[eqn: 89=2 ^{ 6}+2 ^{ 4}+2 ^{ 3}+1=(~1`,~ 0`,~ 1`,~ 1`,~ 0`,~ 0`,~ 1~) _{ 2}].

제곱의 반복에 의해 2의 거듭제곱 [eqn: 1`,~2`,~4`,~8`,~16`,~32`,~64`] 으로 [eqn: (mod7)]의 나머지를 찾을  수 있다. 이 방법은 항상 사용되어진다.

그러나 특별한 경우는 좀 더 간단히 다루어진다. 예를 들면

[eqn: 3^{ 3} ==-1(mod7)]

[eqn: 3^{ 6} ==1(mod7)]

이므로

[eqn: 3^{ 84} ==(3 ^{ 6}) ^{ 14} ==1 (mod7)]

따라서

[eqn: 3^{ 89}=3 ^{ 84} BULLET3 ^{ 3} BULLET3 ^{ 2} ==1 BULLET(-1) BULLET2 ==-2 ==5 (mod7)]

또 다른 예로 2.3절에서 이야기한 페르마 수 [eqn: F_{ t}=2 ^{ 2} ^{ t}+1] 를 보자.

[eqn: F_{ 0}=3], [eqn: F_{ 1}=5], [eqn: F_{ 2}=17], [eqn: F_{ 3}=257], [eqn: F_{ 4}=65537],

[eqn: F_{ 0}]와 [eqn: F_{ 1}]을 제외하고 모든 페르마의수는 끝자리가 7인 것을 알 수 있다.

이런 경우 합동식에 의해 증명해보자. 분명히 [eqn: 2 ^{ 2} ^{ t}`,~t=`2`,~3`,~…]의 끝자리는 6이다. 귀납법에 의해 증명되어진다.

[eqn: 2^{ 2} ^{ 2}=16 ==6(mod10)]

[eqn: 2^{ 2} ^{ 3}=256 ==6(mod10)]

[eqn: 2^{ 2} ^{ 4}=65536 ==6(mod10)]

게다가 [eqn: 2^{ 2 ^{ k} }]의 제곱은 [eqn: (2 ^{ 2} ^{ k}) ^{ 2}=2 ^{ 2 BULLET2 ^{ k} }=2 ^{ 2 ^{ k+1} }] 이다.

어떤 [eqn: t]에 대하여 [eqn: 2^{ 2 ^{ t} } ==6(mod10)]이다. 이 합동식의 제곱은

[eqn: 2^{ 2 ^{ t+1} } ==36 ==6 (mod10)]이다.