페르마의 작은 정리
거듭제곱의 나머지가 만든 질서
계산기를 들고 아무 자연수를 골라 7제곱을 해 보세요. 그 결과에서 처음 골랐던 수를 뺀 다음 7로 나누어 보세요.
어떤 큰 수를 넣어도 나머지가 없이 딱 나누어떨어집니다. 우연의 일치일까요, 아니면 모든 소수 속에 거듭제곱을 제자리로 돌려놓는 마법의 시계가 숨어 있는 걸까요?
이야기
H. Loeffel
Public domain · 위키미디어 공용
소수 하나를 고릅니다. 7로 해 봅시다. 그리고 7로 나누어떨어지지 않는 수 하나, 3을 고릅니다.
이제 을 7로 나눈 나머지를 구해 보세요. 이고 — 나머지가 1입니다.
2로 해 봐도, 5로 해 봐도 그렇습니다. 소수를 11로 바꾸고 을 해 봐도 나머지는 늘 1입니다.
이것이 페르마의 작은 정리입니다.
피에르 드 페르마가 1640년 편지에 적었습니다. 그는 «증명은 보내지 않겠다, 너무 길어서» 라고 썼습니다. 그의 버릇이었습니다.
이름에 「작은」이 붙은 것은 「마지막 정리」와 구별하기 위해서입니다. 마지막 정리는 358년 뒤에야 증명되었지만, 이 작은 정리는 오히려 실용적으로 훨씬 중요합니다.
큰 수가 소수인지 빠르게 판별하는 데, 그리고 인터넷 암호에 쓰입니다.
이 정리가 성립하는 까닭은 목걸이를 세어 보면 보입니다. 색이 a가지인 구슬로 길이 p짜리 목걸이를 만들면 모두 aᵖ가지입니다. 그 가운데 한 가지 색으로만 된 것이 a가지입니다.
나머지를 돌려 보십시오. p가 소수이면 어떤 목걸이든 정확히 p번 돌려야 제자리로 옵니다. 그러니 나머지 aᵖ−a개가 p개씩 묶이고, 따라서 p로 나누어떨어집니다.
⭐ 이 작은 정리가 오늘 인터넷 암호의 뼈대입니다.
큰 수가 소수인지 빠르게 가늠하는 첫 관문입니다. 암호 열쇠를 만들 때 컴퓨터가 이 검사를 먼저 돌립니다.
그리고 이것을 넓힌 오일러 정리 위에 RSA 암호가 서 있습니다 — 지금 이 순간 인터넷을 지키고 있습니다.
계단 넷 — 같은 사실을 네 깊이로
5로 나눈 나머지를 적어 본다
2를 여러 번 곱하면서 5로 나눈 나머지를 적어 봅니다. 2, 4, 8(나머지 3), 16(나머지 1), 32(나머지 2)… 나머지가 규칙적으로 돕니다.
3을 곱해도 마찬가지입니다. 어떤 수를 소수만큼 거듭제곱하면 신기하게도 원래 숫자의 나머지로 되돌아옵니다. 수의 곱셈 속에 톱니바퀴 같은 주기가 있습니다.
거듭제곱하고 나눠 보세요
3⁶ = 729 = 7×104 + 1 — 나머지가 1.
표를 만들어 규칙 찾기
소수 와 서로소인 수 2를 예로 들어 봅시다. 1, 2, 3, 4에 각각 2를 곱하면 2, 4, 6, 8이 됩니다. 이를 5로 나눈 나머지는 2, 4, 1, 3으로 원래의 1, 2, 3, 4가 순서만 바뀌어 그대로 나옵니다.
양쪽을 모두 곱하면 가 되고, 나머지가 같으므로 양변에서 를 약분하면 만 남습니다.
소수인지 알아보세요
이런 수를 의사소수라 합니다.
합동식으로 증명
소수 와 정수 에 대해 가 성립하며, 이면 입니다.
이항정리를 이용한 수학적 귀납법으로도 증명됩니다. 에서 조합수 는 일 때 모두 의 배수이므로 이 성립하여 귀납 단계가 완성됩니다.
카마이클 수
1729 도 카마이클 수입니다 — 라마누잔의 그 수입니다.
소수 판정법
페르마의 작은 정리는 군론에서 유한군 의 임의의 원소 에 대해 가 성립한다는 라그랑주 정리의 잉여류군 에 대한 특수한 경우입니다. 오일러 피 함수를 통해 으로 일반화됩니다.
이 대수적 주기성은 거대한 소수의 합성수 여부를 순식간에 판별하는 밀러-라빈 소수 판정법과 현대 인터넷 보안의 기둥인 RSA 공개키 암호 알고리즘의 심장부로 작동합니다.
밀러–라빈 검사
20 번이면 속을 확률이 1조×1조 분의 1 — RSA 열쇠가 이렇게 만들어집니다.
풀어 보기
페르마의 작은 정리와 나머지. 다음 물음에 답하시오.
(1) 페르마의 작은 정리를 써서 을 7로 나눈 나머지를 구하시오.
(2) 을 소수 13으로 나눈 나머지를 구하시오.
(3) 소수 에 대하여 이 항상 의 배수임을 이용하여, 모든 정수 에 대해 이 항상 30의 배수임을 증명하시오.
(2) 이므로 입니다. (3) 2, 3, 5의 배수임을 보이면 됩니다.
답과 풀이 보기
(1) 나머지는 1 입니다.
페르마의 작은 정리 — 가 소수이고 이면 .
이므로 .
확인 : — 맞습니다.
(2) 나머지는 3 입니다.
이므로 지수를 12 로 나눕니다.
⭐ 30 자리가 넘는 수를 한 줄로 끝냈습니다.
(3) 이므로 셋으로 각각 나누어떨어짐을 보이면 됩니다 (셋이 서로소이므로).
· : — 정리 그대로
· : 이므로
· : 이므로 마찬가지로
셋 다 나누므로 30 으로 나누어떨어집니다.
확인 : 부터 까지 넣어 보면 나머지가 모두 0 입니다.
1640 년 페르마가 증명 없이 편지에 적었습니다. 「증명도 보내고 싶지만 너무 길어질까 두렵다」고 하면서요.
이 정리는 지금 어떤 수가 소수인지 빠르게 가려내는 데 쓰입니다. 인터넷에서 카드 번호를 지켜 주는 RSA 암호의 심장입니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
이 한 줄이 지금 우리의 통신을 지킵니다.
- RSA 암호 — 이 정리를 넓힌 오일러 정리 위에 서 있습니다
- 소수 판별 — 큰 수가 소수인지 빠르게 가늠하는 첫 관문입니다
- 카마이클 수 — 소수가 아닌데 이 성질을 만족하는 얄미운 수도 있습니다
이어지는 장
수를 거듭제곱하다 보면 일정하게 나머지가 1로 되돌아오는 순환의 원리를 만납니다 — 제93장 의 시계 산수가 현대 인터넷 보안을 지키는 공개키 암호의 밑거름이 됩니다.
영감을 받은 곳
피에르 드 페르마가 1640년 10월 18일 친구 프레니클 드 베시(Frénicle de Bessy)에게 보낸 편지에 처음 적어 보냈습니다.