정수론(Number theory)

오일러 피 함수와 페르마 소정리(Euler's totient function and Fermat's little theorem)

φ(n)은 1부터 n까지 n과 서로소⁠(coprime)⁠인 수의 개수. n과 서로소인 a를 그런 수들에 곱하면 그 수들이 같은 길이의 고리로 나뉘고, 그래서 a^φ(n) ≡ 1 (mod n)이다.

a^{\varphi(n)} \equiv 1 \pmod n \quad (\gcd(a,n)=1), \qquad \varphi(n) = n\prod_{p \mid n}\left(1 - \tfrac{1}{p}\right)

먼저 보면 좋은 개념모듈러 연산 최대공약수와 유클리드 호제법

모듈러 연산⁠(modular arithmetic)⁠에서 역수⁠(inverse)⁠가 있는 수, 곧 $n$ 과 최대공약수⁠(greatest common divisor)⁠가 1인 수를 단원이라 부릅니다. $n =$ 의 시계에서 단원(색칠된 점)은 $\varphi(n) =$ 개입니다.

이제 모든 단원에 $a =$ 를 곱해 화살표 $k \to a k$ 를 그려 봅시다.

색이 같은 화살표들이 하나의 고리입니다. 곱하기 a는 단원들을 고리로 돌리는 순열입니다.

핵심은 이것입니다. $a$ 가 단원이면 곱하기 $a$ 는 단원들을 단원들로 보내는 전단사⁠(bijective)⁠입니다. 그리고 단원들은 모두 같은 길이의 고리로 쪼개집니다. 단원 $k$ 에서 출발한 고리가 제자리로 오는 조건 $a^j k \equiv k$ 는, 양변에 $k$ 의 역수를 곱하면 $a^j \equiv 1$ 이 되어 $k$ 와 상관이 없습니다. 그래서 고리 길이는 출발점과 상관없이 $a$ 를 거듭 곱해 처음으로 1이 되기까지의 횟수이고, 이를 $a$ 의 위수라 부릅니다. 고리들이 $\varphi(n)$ 개의 점을 똑같이 나눠 가지니 그 길이는 $\varphi(n)$ 의 약수⁠(divisor)⁠이고, $\varphi(n)$ 번 돌면 누구든 제자리입니다. 그래서 $a^{\varphi(n)} \equiv 1 \pmod n$ 입니다( $\equiv$ 는 $n$ 으로 나눈 나머지⁠(remainder)⁠가 같다는 뜻). 이것이 오일러 정리이고, $n = p$ 가 소수⁠(prime number)⁠이면 $\varphi(p) = p - 1$ 이라 $p$ 의 배수⁠(multiple)⁠가 아닌 모든 $a$ 에 대해 $a^{p-1} \equiv 1$ (페르마 소정리)입니다.

단원끼리 곱하면 다시 단원이고, 1이 곱셈의 항등원⁠(identity element)⁠ 노릇을 하며, 단원마다 역수가 있습니다. 이렇게 결합법칙⁠(associativity)⁠이 성립하는 연산 하나에 대해 닫혀 있고, 항등원과 역원⁠(inverse element)⁠을 갖춘 모임을 군이라 합니다. 위의 "고리 길이는 전체 개수의 약수"라는 논증은 군 이론의 라그랑주 정리(부분군⁠(subgroup)⁠의 크기는 군 크기의 약수)를 이 경우에 쓴 것입니다.

고리 하나에 모든 단원이 들어가는 $a$ 를 원시근⁠(primitive root)⁠이라 합니다. 그러면 단원들은 $a, a^2, a^3, \dots$ 으로 한 줄로 늘어서고, 곱셈은 원을 $\varphi(n)$ 등분한 1의 거듭제곱근⁠(roots of unity)⁠을 도는 회전⁠(rotation)⁠과 똑같아집니다( $n = 7$ 에서 $a = 3$ , $n = 11$ 이나 13에서 $a = 2$ 를 해 보세요. 반면 $n = 11$ 에서 $a = 3$ 은 길이 5인 고리 둘로 갈라져 원시근이 아닙니다). 원시근이 없는 $n$ 도 있습니다. 처음 값 $n = 15$ 에서는 어떤 $a$ 를 골라도 고리 길이가 4를 넘지 않습니다. 원시근이 있는 $n$ 은 2, 4, 홀수 소수의 거듭제곱 $p^k$ , 그 두 배 $2p^k$ 뿐이라는 것을 가우스가 보였습니다. $\varphi(n)$ 의 공식은 소인수분해⁠(prime factorization)⁠한 뒤 각 소인수의 배수를 포함배제 원리⁠(inclusion–exclusion principle)⁠로 빼면 나옵니다. 이 정리 하나 위에 RSA 암호⁠(RSA cryptosystem)⁠가 서 있습니다.

이 개념이 나오는 큰 생각대칭과 불변량

이 개념이 나오는 긴 글

소수 소수를 세는 사람들 소수는 제멋대로 흩어져 있는 것 같다. 그런데 멀리서 세어 보면 로그가 보인다. 정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다.

이 개념 위에 세워진 것

RSA 암호 원시근 소수 판정

이 개념을 언급하는 페이지

포함배제 원리
… = \tfrac{8}{30} 입니다. 이 곱셈 공식이오일러 피 함수의 공식입니다. 같은 셈을 확률로 바꿔 볼 수 있습니다. 다만 "모든 정수 가운데 고르게 하나"를 뽑는 …
소수와 에라토스테네스의 체
… 수가 크면 체를 쓸 수 없습니다. 대신 소수 판정으로 빠르게 가립니다. 많은 판정법의 출발점은페르마 소정리입니다. 소수 p 와 p 의 배수가 아닌 a 에 대해 a^{p-1} 을 p 로 나눈 나머지는 언제나 …
소인수분해
… 약수의 개수는 멱집합의 크기 2^k 이 됩니다. 30의 약수는 2^3 = 8 개입니다. 소인수를 알면오일러 피 함수도 곧바로 계산됩니다. 소인수분해가 한 가지뿐이라는 사실 덕분에 괴델은 수식 하나를 자연수 하나로 바꿔 …
파스칼의 삼각형
… a 가 p 의 배수가 아니면 양변을 a 로 나눌 수 있어 a^{p-1} \equiv 1 이 되는데, 이것이페르마 소정리입니다. 비스듬한 얕은 대각선을 따라 더하면 피보나치 수가 나옵니다. 이 삼각형의 수를 …
모듈러 연산
… 1 을 만드는 x 입니다. 역수가 있는 a 는 정확히 n 과 최대공약수가 1인 수들이고, 그 개수가오일러 피 함수입니다. 최대공약수 g 가 1보다 크면 ax 와 n 이 모두 g 의 배수라 ax 의 나머지도 g 의 …
RSA 암호
… 되돌리는 열쇠가 d 입니다. ed = 1 + k\,\varphi(n) 이고 m 이 n 과 서로소이면,오일러 정리m^{\varphi(n)} \equiv 1 덕분에 (m^e)^d = m \cdot …
1의 거듭제곱근
… 도는 근을 원시 n제곱근이라 하고, 그 개수는 1부터 n까지의 자연수 가운데 n과 서로소인 것의 개수, 곧오일러 피 함수\varphi(n) 입니다. 정수론의 원시근(소수 p로 나눈 나머지에서, 거듭제곱하면 0이 아닌 …
원시근
… 처음 1로 돌아오기까지의 걸음 수가 a 의 위수 입니다. n 과 서로소인 나머지는 \varphi(n) 개(오일러 피 함수)이고, 서로소인 a 의 거듭제곱은 그 안에서만 움직이니 위수는 \varphi(n) 을 넘지 못합니다. 이 …
중국인의 나머지 정리
… 나머지는 ' m 과 서로소인 나머지'와 ' n 과 서로소인 나머지'의 짝과 하나씩 대응합니다. 그래서오일러 피 함수는 \varphi(mn) = \varphi(m)\varphi(n) 를 만족하고, 15에 원시근이 없는 …
디피–헬먼 키 교환
… 수 있습니다. 그래서 실제로는 수백 자리의 p 를, p-1 이 큰 소인수를 갖도록 고릅니다. 이어지는 곳.페르마 소정리g^{p-1} \equiv 1 때문에 g^k 의 주기는 언제나 p-1 의 약수입니다. g 가 원시근이면 …
소수 판정
… 개라 어떤 컴퓨터로도 다 나눠 볼 수 없습니다. 인수를 찾지 않고도 합성수임을 알아낼 방법이 필요합니다.페르마 소정리는 n 이 소수이면 n 의 배수가 아닌 모든 a 에 대해 a^{n-1} \equiv 1 \pmod n …
이항계수
… 나머지는 a^p + 1 , 곧 a + 1의 나머지와 같으므로) a^p 를 p로 나눈 나머지가 a와 같다는페르마 소정리가 증명됩니다. 겹치는 집합들의 합집합 크기(집합의 크기)를 세는 포함배제 원리에도 이항계수가 숨어 …
군
… p − 1과 'p로 나눈 나머지의 곱셈'(p는 소수)에 적용하면, p의 배수가 아닌 모든 a에 대해페르마의 소정리a^{p-1} \equiv 1 \pmod p 가 곧바로 나옵니다. a, a², a³, …은 k번째에서 …
정수론
… 18 + 2 이니 128을 7로 나누면 2가 남습니다. 오일러는 이 정리를 소수가 아닌 법으로 넓혔고(오일러 피 함수), 가우스는 오일러와 르장드르가 추측한 이차 상호 법칙을 1796년에 처음 증명해 이 책에 …
작도 가능한 수
… 알려진 것은 3, 5, 17, 257, 65537 다섯뿐입니다)들의 곱일 때, 그리고 그때뿐입니다.오일러 피 함수로 말하면 φ(n)이 2의 거듭제곱일 때입니다. 1796년 가우스가 정17각형을 작도할 수 있음을 …

이 페이지가 가리키는 개념

단사·전사·전단사 레온하르트 오일러 소수와 에라토스테네스의 체 피에르 드 페르마 군 조제프루이 라그랑주 원시근 1의 거듭제곱근 회전 행렬 카를 프리드리히 가우스 소인수분해 포함배제 원리 RSA 암호