페르마 소정리 참고자료

[한번만말하겠다!]

페르마 소정리를 쓰면,

p가 소수이고, a와 p가 서로소이면 a^(p-1) ≡ 1 (mod p)이다

다양한 곳에 쓰인다죠? 개념님이 말씀하셨듯이 암호학에도 쓰이죠. 예를들어 공개키 암호는 이것을 이용한 것이라는군요. 공개키 암호에대해 매쓰레터합본 몇권인가에 있더군요. 주위 도서관에 가서 보세요.

아래에서는 이 정리를 이용해 "거듭제곱의 주기성"으을 알아냈고 그것으로 문제를 풀었습니다

2^55을 7로 나눈 나머지가 무엇일까?라는 문제를 생각해보죠

합동식으로 표현하면

2^55 ≡ x (mod 7) 인 0이상 7미만의 정수 x를 찾는 것입니다

페르마의 소정리의 a와 p에 2와 7을 대입해보죠

2^6 ≡ 1  (mod 7)

6에 9를 곱하면 54가 되니까 양변을 9제곱하죠

2^54 ≡ 1 (mod 7)

이제 2^55을 만들기 위해 양변에 2를 곱합니다

2^55 ≡ 2 (mod 7)

결국 x=2 입니다.

만약 3^55의 일의자리를 묻는다고 하죠. 이것을 나머지 문제로 바꿔봅시다

3^55를 10으로 나눈 나머지는? 이것을 합동식으로 바꿔봅시다

3^55 ≡ x (mod 10)인 0이상 10미만의 정수 x를 구하라

페르마 소정리에 a=3, p=10을 대입하시다...............라고 하면 안되죠. 10은 소수가 아니기 때문입니다. p가 소수가 아닐때도 이와 유사한 것이 있습니다. 오일러가 페르마의 소정리를 확장했습니다.

a와 n이 서로소일때, a^Φ(n) ≡ 1 (mod n)

Φ(n)는 "n보다 작은 자연수중 n과 서로소인 수의 개수"입니다

만약 n이 소수라면 1,2,3,4,...,n-1모두 n과 서로소이므로 Φ(n)=n-1이되어 페르마의 소정리가 됩니다.

이제 이 오일러의 정리에 a=3, n=10을 대입하죠

10미만의 수중 10과 서로소인 수는 1,3,7,9이므로 Φ(n)=4입니다

3^4 ≡ 1 (mod 10)

4에 13을 곱하면 52이므로 양변을 13제곱합니다

3^52 ≡ 1 (mod 10)

3^55을 만들기 위해 양변에 3^3을 곱합니다

3^55 ≡ 3^3 (mod 10)

3^3 ≡ 7 (mod 10)이므로 3^55 ≡ 7 (mod 10)

따라서 3^55의 일의자리수는 7입니다

사실 3^55의 일의자리수를 알기위해서는 3을 몇번 거듭제곱해서 주기를 구하면됩니다.

그러나, 만약에 27^27의 십의자리수를 묻는다고 합시다. 27를 여러번 거듭제곱해서 구하는 것보다. 27^27를 100으로 나눈 나머지를 구한다고 접근해서 27^27 ≡ x (mod 100)인 x를 구하는 문제로 바꾼다면, 좀 더 쉬워질 것입니다. 백의 자리수나 천의 자리수를 물을 때도 마찬가지 입니다.

더 알아야 할 것은 Φ(n)를 구하는 방법입니다

n의 인수분해가 a^j * b^k * c^l 이라면

Φ(n) = Φ(a^j) * Φ(b^k) * Φ(c^l) = (a^j - j) * (b^k - k) * (c^l - l) 임을 이용해서 Φ(n)을 좀더 쉽게 구할 수 있습니다

마지막으로 합동식도 고등학교 과정에서 안배우는데 a≡b (mod n)이라함은 a-b가 n의 배수라는 말입니다 a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지가 같다고 할 수도 있습니다 만약 b가 0이상 n미만일때는 a를 n으로 나눈 나머지가 b가 된다는 것을 의미하죠

그럼 이만 꾸벅(--)(__)(--)

[개념]

^^*멋져요~!

[F킬러]

오오.. +_+