오일러 피 함수 해설

1부터 10까지의 수를 쓰고 10과 공약수가 있는 수를 모두 지워 보세요. 1, 3, 7, 9 네 개가 남습니다. 이 개수 φ(10) = 4가 오일러 피 함수로, 분수와 시계에서부터 온라인 결제를 지키는 암호에 이르기까지 정수론에서 가장 많이 쓰이는 함수 중 하나입니다.

1부터 30까지의 수가 격자에 놓여 있고 30과 서로소인 여덟 개가 채워져 있으며, 공식 φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8과 소수가 직선 위에 놓인 φ(k) 그래프가 함께 있는 그림
1부터 30까지의 수가 격자에 놓여 있고 30과 서로소인 여덟 개가 채워져 있으며, 공식 φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8과 소수가 직선 위에 놓인 φ(k) 그래프가 함께 있는 그림

서로소인 수 세기

두 수의 최대공약수가 1이면 두 수는 서로소입니다. φ(n)은 1부터 n까지의 k 중 gcd(k, n) = 1인 것을 셉니다. φ(9) = 6, φ(10) = 4, φ(12) = 4, φ(1) = 1입니다. 같은 개수가 여러 곳에서 나타납니다. 0과 1 사이의 k/n 중 이미 기약분수인 것의 개수, n시간 시계에서 바늘이 모든 시각을 지나게 하는 보폭의 개수, 그리고 n을 법으로 역원을 가져서 k × x ≡ 1 (mod n)을 풀 수 있는 k의 개수입니다.

곱셈 공식

n을 나누는 소수가 p₁, p₂ …이면 φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …입니다. 이유는 체입니다. 모든 수의 절반은 짝수이므로 2의 배수를 빼면 1 − 1/2의 비율이 남고, 남은 수 중 세 개에 하나는 3의 배수이며, 이런 식으로 계속됩니다. 중국인의 나머지 정리에 따라 서로 다른 소수에 대한 조건은 독립이므로 비율들은 그냥 곱해집니다. 100 = 2² × 5²이면 100 × 1/2 × 4/5 = 40입니다. 두 가지 성질이 같은 결과를 다른 형태로 줍니다. φ(p^k) = p^(k−1)(p − 1)이고, m과 n이 서로소이면 φ(mn) = φ(m) φ(n)이므로 φ(100) = φ(4) × φ(25) = 2 × 20 = 40입니다.

오일러 정리

페르마는 1640년에 소수 p와 p로 나누어떨어지지 않는 모든 a에 대해 a^(p−1) ≡ 1 (mod p)임을 알아챘습니다. 오일러는 일반적인 형태를 증명해 1763년에 발표했습니다. gcd(a, n) = 1이면 a^φ(n) ≡ 1 (mod n)입니다. 증명은 짧습니다. n과 서로소인 φ(n)개의 수에 각각 a를 곱하면, 곱은 다시 n과 서로소이고 n을 법으로 모두 다르므로 같은 수들을 순서만 바꾼 것이 되고, 두 곱을 비교하면 a^φ(n) ≡ 1이 남습니다. 주어진 a에 대해 성립하는 가장 작은 지수가 그 위수이며 항상 φ(n)을 나눕니다. 모든 a에 대해 동시에 성립하는 가장 작은 지수가 카마이클 함수 λ(n)입니다. 561 = 3 × 11 × 17에서는 λ(561) = 80이 560을 나누므로, 561은 소수가 아닌데도 561과 서로소인 모든 a에 대해 a^560 ≡ 1 (mod 561)입니다. 이것이 가장 작은 카마이클 수이며, 페르마 판정법만으로는 어떤 수가 소수임을 증명할 수 없는 이유입니다.

레온하르트 오일러, 야코프 에마누엘 한트만의 초상. 그는 1763년에 페르마의 관찰을 일반화해 발표했다. a와 n이 서로소이면 a^φ(n) ≡ 1 (mod n).
레온하르트 오일러, 야코프 에마누엘 한트만의 초상. 그는 1763년에 페르마의 관찰을 일반화해 발표했다. a와 n이 서로소이면 a^φ(n) ≡ 1 (mod n).

가우스의 약수 합과 평균

n의 약수 d에 대해 φ(d)를 모두 더하면 언제나 n이 다시 나옵니다. 12라면 φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12입니다. 가우스는 1801년 『산술 연구』에서 이를 증명했습니다. 분수 1/12, 2/12 … 12/12를 기약분수로 만들어 분모별로 나누어 보면 그 이유가 보입니다. 평균적으로 φ(k)는 약 0.61 k입니다. φ(k)/k의 평균은 6/π² ≈ 0.6079에 가까워지며, 이는 임의로 고른 두 정수가 서로소일 확률이기도 합니다. φ(1) + … + φ(N)은 3N²/π²에 가깝습니다. N = 1,000이면 합은 304,192이고 3N²/π² ≈ 303,964입니다.

카를 프리드리히 가우스, 크리스티안 알브레히트 옌센의 1840년 초상. 1801년의 Disquisitiones Arithmeticae에서 합동 기호 a ≡ b (mod n)를 도입했다.
카를 프리드리히 가우스, 크리스티안 알브레히트 옌센의 1840년 초상. 1801년의 Disquisitiones Arithmeticae에서 합동 기호 a ≡ b (mod n)를 도입했다.

결코 나타나지 않는 값

3 이상의 모든 n에서 φ(n)은 짝수입니다. n과 서로소인 수는 k와 n − k의 쌍으로 나타나기 때문입니다. 모든 짝수가 값이 되는 것도 아닙니다. 14, 26, 34, 38, 50이 결코 나타나지 않는 처음 값들이고, 반면 24는 35부터 90까지 서로 다른 열 개 수의 값입니다. 이들을 찾는 것은 유한한 탐색입니다. n을 나누는 각 소수 p에 대해 p − 1이 φ(n)을 나누어야 하기 때문입니다. 1907년 로버트 카마이클은 정확히 한 번만 나오는 값은 없다고 주장했습니다. 그의 증명은 틀렸고, 이 주장은 아직 미해결이며, 예외가 있다면 10^(10^10)보다 커야 합니다. D. H. 레머는 1932년에 합성수 n에 대해 φ(n)이 n − 1을 나눌 수 있는지 물었는데, 알려진 예는 없습니다.

RSA 속의 피 함수

RSA는 큰 소수 p와 q 두 개를 골라 n = pq와 지수 e를 공개합니다. φ(n) = (p − 1)(q − 1)이므로 n을 소인수분해할 수 있는 사람은 φ(n)을 계산할 수 있고, 거기서 e × d ≡ 1 (mod φ(n))인 비밀 지수 d를 구할 수 있습니다. 그러면 오일러 정리가 (m^e)^d ≡ m (mod n)을 보장합니다. 교과서 예제 n = 3233 = 61 × 53에서는 φ(n) = 3,120, e = 17, d = 2,753입니다. 많은 구현은 대신 λ(n) = lcm(p − 1, q − 1)을 쓰는데, 여기서는 780이라 더 작은 d = 413이 나옵니다. 600자리 RSA 모듈러스의 φ(n)을 계산하는 것은 그것을 소인수분해하는 것만큼 어렵습니다. n과 φ(n)을 알면 제곱근 한 번으로 두 소수가 나오기 때문입니다.

론 리베스트, 아디 샤미르, 렌 애들먼(왼쪽부터)
론 리베스트, 아디 샤미르, 렌 애들먼(왼쪽부터)

직접 살펴보기

계산기를 열고 10^18 이하의 아무 n이나 입력하면 φ(n)과 소인수, 공식이 나타납니다. 500까지는 1부터 n까지의 수가 그려지는데, 서로소인 수는 채워지고 나머지는 n과 공유하는 가장 작은 소수의 색으로 칠해지므로 곱셈 공식이 셀 수 있는 체가 됩니다. 수 a를 골라 오일러 정리를 확인하거나, ‘그래프’로 바꿔 소수가 직선 φ(p) = p − 1 위에 놓인 100,000까지의 φ(k)를 보거나, ‘역산’으로 바꿔 φ(n) = m인 모든 n을 찾아보세요.

자주 묻는 질문

왜 φ(1) = 1인가요?

gcd(1, 1) = 1이기 때문입니다. 1부터 1까지의 유일한 수는 1과 서로소입니다. 이 관례는 공식이 계속 성립하게 해 주기도 합니다. 예를 들어 n의 약수에 대한 가우스의 합은 n = 1일 때 그냥 φ(1) = 1입니다.

φ는 소수 계량 함수와 같은 것인가요?

아닙니다. π(n)은 n 이하의 소수를 세고, φ(n)은 n 이하의 수 중 n과 서로소인 수를 셉니다. φ(10) = 4는 1, 3, 7, 9를 세고, π(10) = 4는 2, 3, 5, 7을 셉니다. 여기서 같은 것은 우연입니다. φ(12) = 4이지만 π(12) = 5입니다.

φ(n)은 얼마나 빨리 계산할 수 있나요?

n을 소인수분해할 수 있는 만큼 빠릅니다. 소인수를 알면 곱셈 몇 번이면 되지만, 모르면 빠른 방법이 알려져 있지 않으며 RSA는 바로 이 점에 기대고 있습니다. 10^18 이하의 수는 브라우저에서 몇 밀리초면 소인수분해되지만, 수백 자리 수는 몇 년이 걸릴 수 있습니다.

n에 비해 φ(n)이 가장 작은 수는 어떤 수인가요?

작은 소인수를 많이 가진 수입니다. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)…은 어떤 소수가 n을 나누는지에만 달려 있고 그 거듭제곱과는 무관합니다. 2의 거듭제곱이면 정확히 1/2이고, 30 = 2 × 3 × 5이면 8/30으로 약 27%입니다. 처음 15개 소수의 곱인 614,889,782,588,491,410은 φ(n)/n ≈ 14%로, 10^18 이하의 모든 수 중 가장 낮습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

피 함수 계산기 열기