7. 정수론: 오일러의 피 함수과 페르마의 소정리 (Number Theory: Euler's Phi Function and Fermat's Little Theorem)
오일러의 피 함수Euler's Totient(phi) Function
오일러의 피 함수 ϕ(n)는 어떤 양의 정수 n에 대해, 0부터 n까지의 정수 중 n과 서로소인 정수의 갯수를 나타내는 함수이다.
예를들어, ϕ(6)은 0 6중 1,5만이 6과 서로소이므로 2이다.
오일러의 정리Euler's Theorem
만약 gcd(n,k)=1이면, (n,k가 서로소이면) kϕ(n)≡1(modn)이다.
예를들어, 4와 9가 서로소이므로, 4ϕ(9)=46=4096≡1(mod9)이다.
만약 n,k가 서로소이면, k는 (modn)에 대한 k−1을 갖는다.
n 이하의 자연수 중, n과 서로소인 자연수들의 집합을 S라 하자.
S의 원소의 갯수는 ϕ(n)이다.
S={s0,s1,⋯sn}이라 하자.
n과 서로소인 어떤 수 a를 S에 곱하면
aS={as0,as1,⋯asn}
이때, n에 대해 서로소인 두 수의 곱은 역시 n과 서로소이므로, aS의 모든 원소는 n과 서로소이다.
또한, aS의 원소들을 n으로 나눈 나머지는 S의 원소들의 재배열이 되므로, S의 모든 원소의 곱과 aS의 모든 원소의 곱은 n으로 나눈 나머지가 같다.
b1⋯bϕ(n)≡aϕ(n)b1⋯bϕ(n)(modn)
aϕ(n)≡1(modn)
예제
n=6면, S={1,5}다.
a=5로 놓으면 aS={5,25}이므로,
1⋅5≡52⋅5⋅25(mod6)
페르마의 소정리Fermat's Little Theorem
페르마의 소정리는 오일러의 정리의 따름 정리이다.
소수 p와 서로소인 임의의 정수 a에 대해,
ap−1≡1(modp)
가 성립한다는 것이다.
예를들어, p=7,a=8로 놓고 보면, 86≡1(mod7)이다.
페르마의 소정리는 오일러의 정리에 n 자리에 p를 대입하여 증명할 수 있다.
kϕ(p)≡1(modp)인데, 이때, ϕ(p)는 소수이므로 p−1이 된다.
kp−1≡1(modp)로 바로 증명이 되었다.
'학부 수업 > 이산수학' 카테고리의 다른 글
9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem) (2) | 2020.10.18 |
---|---|
8. RSA 암호화 (RSA Encryption Algorithm) (1) | 2020.10.17 |
6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption) (2) | 2020.10.17 |
5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime) (2) | 2020.10.17 |
4. 정수론: 최대공약수 (Number Theory: Great Common Divisor) (1) | 2020.10.14 |
댓글
이 글 공유하기
다른 글
-
9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem)
9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem)
2020.10.18 -
8. RSA 암호화 (RSA Encryption Algorithm)
8. RSA 암호화 (RSA Encryption Algorithm)
2020.10.17 -
6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption)
6. 정수론: 암호화, 복호화 (Number Theory: Encryption and Decryption)
2020.10.17 -
5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)
5. 정수론: 서로소와 합동식 (Number Theory: Congruent and Relatively Prime)
2020.10.17
댓글을 사용할 수 없습니다.