Skip to content
총 11개의 글이 있습니다.
오일러 피 함수
오일러 피 함수는 1~n 범위 중 n과 서로소인 숫자의 갯수를 구하는 함수이다.
1부터 6까지의 정수 중 6과 서로소인 수는 1, 5 두 개이므로 φ(6) = 2이다.
1부터 10까지의 정수는 모두 11과 서로소이고, 11은 자신과 서로소가 아니므로, φ(11) = 10이다.
1은 자기 자신과 서로소이므로, φ(1) = 1이다.
오일러 정리
오일러 정리는, 정수 a 및 양의 정수 n이 주어졌고 a와 n이 서로소일 때 아래 식이 성립한다는 내용이다.
a^φ(n) ≡ 1 (mod n)
페르마 소정리와 유사한 논리로 증명할 수 있다.
n과 서로소인 1부터 n까지의 정수를 r₁, r₂, …, r_φ(n)이라 하자. 이들의 개수가 바로 φ(n)개이다.
a가 n과 서로소일 때, ar₁, ar 유클리드 호제법
두 정수 a를 b로 나눈 값을 아래처럼 표현하면 (a ≥ b)
a = bq + r (단, 0 ≤ r &x3C; b)
다음 정리가 성립한다.
(a, b) = (b, r)
즉, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질을 나머지가 0이 될 때까지 반복하면 마지막에 남는 0이 아닌 수가 gcd(a, b)이다.
예시
(1071, 1029)= (1029, 42)= (42, 21)= (21, 0)= 21
따라서 gcd(1071, 1029) = 21
증명
a,b ∈ Z 이고 a ≥ b 라 하자.
두 정수 a를 b로 나눈 값을 아래처럼 표현할 수 있다.
a = bq + r, 0 ≤ r &x3C; b
(a, b) = d 라고 하고, a = dα, b = dβ 라 해보