페르마 정리와 오일러 정리

페르마 정리(Fermat Theorem)

• 만약 p가 소수라면 a는 p에 의해 나누어지지 않는 양의 정수이면, 다음이 성립한다

  a^(p-1) ≡ 1 mod p

 

test

• a=7, p= 19, 7^18 ≡ x mod 19,    x=?

• 7^2 = 49 ≡ 11 mod 19

• 7^4 = 121 ≡ 7 mod 19

• 7^8 = 49 ≡ 11 mod 19

• 7^16 = 121 ≡ 7 mod 19

• a^(p-1) = 7^18 = 7^16 * 7^2 ≡ 7*11 ≡ 1 mod 19

 

페르마 정리의 다른 유용한 형태

• 만약 p가 소수이고 a가 양의 정수라 a^p ≡ a mod p가 성립한다.

• 예) a=3, p=5, 3^5 = 243 ≡ 3 mod 5

• 예) a=10, p=5, 10^5 = 100000 ≡ 10 mod 5 ≡ 0 mod 5

 

오일러 정리

• 오일러의 Totient 함수, 정수론에서 오일러의 totient 함수는

라고 표기된다.

 

 

 

 

• 오일러 정리

서로소인 모든 a와 n에 대한 관계를 나타낸다.

example)

 

확장된 유클리드 알고리즘

• 유클리드 알고리즘

- 두 양의 정수들에 대한 최대 공약수 찾기

• 확장된 유클리드 알고리즘

- 한 수에 대한 곱셈의 역원 결정

- 만약 GCD(d,f)=1이라면 그때 d는 modulo f 상에서 곱셈에 대한 역원을 갖는다.

- 양의 정수 d<f에 대해, dd^-1=1 mod f인 d^-1<f가 유일하게 존재

- 알고리즘은 d^-1를 찾아주는 것이다

예, 3* d^-1 = 1 mod 5 가 되는 것은 ? 2, 7, …