[정수론], Fermat와 Euler 정리

오일러 함수에 설멍하자면 완전잉여계, 기약잉여계를 사용할 때 Zm, Zp에 대한 값으로 해당 식에 답이 몇 개 존재하는지 판별할 수 있는 함수이다.

 

∂(m)  = |Z* m|이랑 동일하다.

 

m이 거듭제곱, 소수, 합성수일 때 오일러 함수를 계산할 때 식이 달라진다.

 

한 자리 소수일 경우: ∂(m)  = m-1 

합성수 일 경우: ∂(m) = (m-1) x (n-1)  

거듭제곱 일 경우= m^2 - m^1 

 

 

와 같이 계산하면 된다.

 

예시를 보여주면  ∂(3)  = 3-1  = 2,  ∂(6) = (3-1) x (2-1) = 2 x 1 = 2 , ∂(9) = (3^2) - (3^1) = 9 - 3 = 6 과 같다.

 값이 클 경우는 어떻게 계산하나요?

 

소인수분해 했을 때 나왔던 값만 넣어주면 되며 이 식에는 지수가 들어가지 않는다.

 

 

페르마 정리는 a^ ∂(p) ≡ 1 (mod p) 또는 a^p-1 ≡ 1 (mod p)라는 점이다. (첫번째 버전)

어떠한 양의 정수가 소수인가를 판정하는데 필요한 정리이다.

 

두번째 버전에선 a^p ≡ a (mod p)를 만족한다고 해서 p가 반드시 소수는 아니하다.