- 소수(직선 φ(p) = p − 1 위)
- 다른 수
- 여러분의 n
오일러 피 함수 계산기
1부터 12까지의 수 중 12와 공약수가 없는 수는 1, 5, 7, 11뿐이므로 φ(12) = 4입니다. 오일러 피 함수는 모든 n에 대해 이런 서로소인 수를 셉니다. 10^18 이하의 수를 입력하면 φ(n)과 소인수, 풀어 쓴 곱셈 공식을 얻고, 1부터 n까지의 수 중 서로소인 수가 강조된 모습을 보고, 오일러 정리를 확인하고, 한 번에 최대 100,000개의 수에 대한 φ(k)를 그리거나, 주어진 φ(n)을 갖는 모든 n을 찾을 수 있습니다. 10^18 이하의 정수 n을 입력하거나 풀이 예제를 고르세요. 타일에는 φ(n), n의 소인수, 1부터 n까지의 수 중 n과 서로소인 수의 비율, 약수의 개수가 표시되고, 단계에서는 곱셈 공식을 여러분의 수로 풀어 씁니다. n = 500까지는 1부터 n까지의 수가 그려집니다. n과 서로소인 수는 채워지고, 나머지는 n과 공유하는 가장 작은 소수의 색으로 표시됩니다. 수를 가리키면 n과의 gcd가 보이고, 클릭하면 오일러 정리의 a로 사용됩니다. ‘그래프’는 한계까지의 모든 k에 대해 φ(k)를 보여 주며, 점을 클릭하면 그 수가 열립니다. ‘역산’은 φ(n) = m인 모든 n을 나열하며, 하나를 클릭하면 열립니다.
작동 원리
- 10^18 이하의 정수 n을 입력하거나 φ(60), RSA 모듈러스, 카마이클 수 561 같은 풀이 예제를 고르세요.
- φ(n), 소인수, 여러분의 수로 쓴 곱셈 공식을 읽으세요. 500까지는 1부터 n까지의 수를 가리키면 n과의 gcd가 보이고, 하나를 클릭하면 그 수로 오일러 정리를 확인할 수 있습니다.
- ‘그래프’로 바꾸면 100,000까지의 모든 k에 대한 φ(k)를, ‘역산’으로 바꾸면 φ(n) = m인 모든 n을 볼 수 있습니다.
φ(n)을 계산하는 방법
n을 소인수분해하고, n을 나누는 각 소수 p마다 n에 (1 − 1/p)를 곱합니다. 60 = 2² × 3 × 5이면 60 × 1/2 × 2/3 × 4/5 = 16입니다. 지워 나가도 같은 개수가 나옵니다. 60개의 수 중 30개는 짝수이고, 30개의 홀수 중 10개는 3의 배수이며, 남은 20개 중 4개는 5의 배수이므로 16개가 남습니다. 소수의 거듭제곱에 대한 공식은 φ(p^k) = p^(k−1)(p − 1)이고, 값들을 곱하면 φ(60) = 2 × 2 × 4입니다. 어려운 부분은 소인수분해입니다. 계산기는 시행 나눗셈, 밀러–라빈 소수 판정법, 폴라드 로 알고리즘을 사용하므로 9자리 소수 두 개를 곱한 18자리 수도 1초도 걸리지 않습니다.
피 함수가 쓰이는 곳
φ(n)은 0과 1 사이의 k/n 중 이미 기약분수인 것의 개수, n시간 시계에서 바늘이 모든 시각을 지나게 하는 보폭의 개수(12시간 시계에서는 1, 5, 7, 11), 그리고 n을 법으로 역원을 갖는 수의 개수를 셉니다. 오일러는 n과 서로소인 모든 a에 대해 a^φ(n) ≡ 1 (mod n)임을 증명했고, RSA 암호는 이를 바탕으로 합니다. n = 3233 = 61 × 53이면 φ(n) = 60 × 52 = 3,120이고, 공개 지수 17의 비밀 짝은 2,753입니다. 17 × 2,753 = 15 × 3,120 + 1이기 때문입니다.
자주 묻는 질문
오일러 피 함수란 무엇인가요?
φ(n)은 1부터 n까지의 정수 중 n과 1 말고는 공약수가 없는 수의 개수입니다. 1, 2, 4, 5, 7, 8은 9와 서로소이고 3, 6, 9는 인수 3을 공유하므로 φ(9) = 6입니다. 관례상 φ(1) = 1입니다. 오일러는 1760년대에 이 함수를 연구했고, 가우스가 1801년에 기호 φ를, 제임스 조지프 실베스터가 1879년에 영어 이름 totient를 붙였습니다.
소수의 φ 값은 얼마인가요?
p − 1입니다. 1부터 p − 1까지의 모든 수가 소수 p와 서로소이므로 φ(97) = 96입니다. 소수의 거듭제곱에서는 p의 배수만 공약수를 가지므로 φ(p^k) = p^k − p^(k−1)이고, φ(81) = 81 − 27 = 54입니다.
오일러 정리는 무엇을 말하나요?
a와 n이 서로소이면 a^φ(n)을 n으로 나눈 나머지는 1입니다. n = 60, a = 7이면 φ(60) = 16이고 7^16 ≡ 1 (mod 60)입니다. 페르마의 소정리는 n이 소수인 경우입니다. 더 작은 지수로 충분한 경우도 많습니다. 7^4 = 2,401 = 40 × 60 + 1입니다. n과 서로소인 모든 a에 대해 성립하는 가장 작은 지수는 카마이클 함수 λ(n)이며, 60에서는 4입니다.
두 수의 피 함수 값이 같을 수 있나요?
네, 대개 여러 개입니다. n = 35, 39, 45, 52, 56, 70, 72, 78, 84, 90일 때 φ(n) = 24입니다. 어떤 짝수는 결코 φ의 값이 되지 않으며 그중 가장 작은 것은 14이고, n = 3부터 φ(n)은 짝수이므로 1보다 큰 홀수도 값이 되지 않습니다. 로버트 카마이클은 1907년에 정확히 한 번만 나오는 값은 없다고 주장했습니다. 이는 아직 증명되지 않았고, 케빈 포드는 1998년에 예외가 있다면 10^(10^10)보다 커야 함을 보였습니다.
얼마나 큰 수를 입력할 수 있나요?
10^18 이하의 모든 정수입니다. 계산기는 브라우저에서 정확한 정수 연산으로 소인수분해하므로 φ(10^18) = 4 × 10^17과 φ(999,999,866,000,004,473) = 999,999,864,000,004,608이 마지막 자리까지 정확합니다. 1부터 n까지의 수는 500까지 그려지고, 그래프는 100,000까지, 역산은 10^10 이하의 값에 대해 작동합니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동