Euler Theorem ...

○Euler Therem

 ▷자연수 n과 정수 a에 대해

 ▷gcd(a, n) = 1이면, a^φ(n) = 1 mod n 이다.

 ▷= 모든 a ∈ Zn*에 대해 a^φ(n) = 1 mod n이다.

 

 ▶증명

  ▶Lemma 1

   ▷S = {r_1, ... , r_k}를 reduced residue system mod n이라고 하자.

    ▷모든 r_i ∈ S와 n은 서로소이다.

   ▷임의의 정수 a에 대해서 coset aS = {ar_1, ... , ar_k} 또한 reduced residue system mod n이다.

 

 

  ▶Lemma 2

   ▷a = b mod n이고, c = d mod n일때

   ▷ac = bd mod n이다.

 

  ▶증명

   ▷S ={r_1, ... r_k} 와 aS = {ar_1, ... ar_k}에서 ar_i = r_j mod n인 Unique r_j가 존재한다.

   ▷r_1...r_k = a^φ(n) r_1...r_k mod n

   ▷(1 - a^φ(n))은 n으로 나누어 떨어진다.

   ▷a^φ(n) = 1 mod n

 

 

○Fermat's Little Theorem

 ▷p가 소수일때,

 ▷정수 a에 대해 a^p = a mod p이다.

 ▷= 모든 a ∈ Zp*에 대해 a^p = a mod p이다.

 

 ▶증명

  ▶gcd(a, p) = 1일때

   ▷Euler Theorem: a^(p-1) = 1 mod p

 

  ▶gcd(a, p) ≠ 1일때

   ▷a = kp의 형태이다.

   ▷a^p - a = a(a^(p-1) - 1) = kp(a^(p-1) - 1) = 0 mod p

   ▷a^p = a mod p

 

 

○Generators in Zp*

 ▷p가 소수일때, 

 ▷Zp*는 order p-1을 가지는 cyclic group이다.

 ▷generator의 개수는 φ(p-1)개 이다.

 ▷= φ(ord(Zp*))

 

 ▶증명

  ▶Lemma 3

   ▷a, b ∈ G일때

    ▷G: abelian Group

    ▷ord(a) = u, ord(b) = v

   ▷G는 order가 lcm(u,v)인 원소를 가지고 있다.

   ▷= G는 cyclic Group이고, generator를 가지고 있다.

 

  ▶Lemma 4

   ▷ord(a) = h일때

    ▷a^h = e

   ▷ord(a^k) = h / gcd(h, k)이다.

 

  ▶증명

   ▷Lemma 3을 통해 cyclic group이며, generator가 최소 하나 있다는 사실을 확인했고,

   ▷Lemma 4의 a = generator라고 할 때,

   ▷ord(a^k) = p-1 / gcd(p-1, k) = p-1을 만족하는 k는 총 φ(p-1)개 있다. (1≤k≤p-1)

   ▷generator: a^k들