페르마정리 및 가우스정리

페르마정리 및 가우스정리

군 Z/nZ의 두 원소 a + nZ, b + nZ에 대해 곱셈 연산을 (a + nZ)(b + nZ) := (ab) + nZ

으로 정의하면 Z/nZ은 환이 된다. 이 때 환 Zn와 Z/nZ 사이에 함수 φ : Z/nZ → Zn

을 φ(a + nZ) := a (mod n)으로 정의하면 φ는 환동형사상이 된다.

Theorem 0.1. F 가 체일 때 0_F가 아닌 원소들의 집합 F^×은 곱셈 연산에 대해 군이 된다.

Proof. 3주차 연습문제 4번의 특수한 경우이다.

Example 0.2. p가 소수일 때 Zp는 체가 된다. 따라서 Z^×p = Zp − {0}는 곱셈에 대해 위수가 p − 1인 군이 된다. 따라서 b ∈ Z^×p에 대해 b^p−1= 1이다.

Theorem 0.3. (Little Theorem of Fermat) a ∈ Z이고 p는 소수일 때 p가 a를 나누지 않으면 p는 a^p−1− 1을 나눈다.

Proof. 환동형사상 φ : Z/pZ → Zp, φ(a + pZ) := a (mod p)을 생각하자. a /∈ pZ 이면 φ(a + pZ) ∈ Z^×p이고 따라서 φ(a + pZ)^p−1= 1이다. 즉, a^p−1≡ 1 (mod p)이다.

Corollary 0.4. a ∈ Z이고 p가 소수이면 a^p ≡ a (mod p)이다.

Proof. 학생들이 직접 시도해 볼 것

Example 0.5. 8¹⁰³을 13으로 나누었을 때 나머지를 구해보자. 13이 소수 이고 8 - 13 이므로 페르마의 정리에 의해 8¹²≡ 1 (mod 13) 이다. 따라서

8¹⁰³ ≡ (8¹²)⁸8⁷ ≡ 8⁷ ≡ 64³8 ≡ (−1)³8 ≡ −8 ≡ 5 (mod 13) 이다.

Example 0.6. 2¹¹²³¹− 1은 11의 배수가 되지 않음을 보여보자. 위와 마찬가지로 2¹⁰≡ 1 (mod 11)을 이용하면

2¹¹²³¹≡ (2¹⁰)¹¹²¹2³ ≡ 2³ (mod 11) 임을 알 수 있다.

Example 0.7. 임의의 정수 n에 대해 n³³− n은 15의 배수가 됨을 보여보자. 15 = 3 · 5이고 3, 5가 소수이므로 n³³ − n이 3, 5의 공배수임을 보이면 된다. n이 3의 배수가 아니라고 하자. 그러면 페르마의 작은 정리에 의해 n² ≡ 1 (mod 3) 이다.

따라서

n³³− n ≡ (n²)¹⁶n − n ≡ n − n ≡ 0 (mod 3) 이다. 같은 원리로 n이 5의 배수가 아닐 때 n⁴ ≡ 1 (mod 5)이므로

n³³− n ≡ (n⁴)⁸n − n ≡ n − n ≡ 0 (mod 5) 임을 알 수 있다.

Theorem 0.8. G_n은 Zn에서 영인자가 아니고 0도 아닌 원소들의 집합이라 하자.

그러면 G_n은 Zn의 곱셈 연산에 의해 군이 된다.

Proof. (i) G_n은곱셈에 대해 닫혀있다;

a, b ∈ G_n에 대해 ab /∈ G_n이라 하자. 그러면 (ab)c = 0 이고 c 6= 0인 c ∈ Zn가 존 재한다. 따라서 (ab)c = a(bc) = 0 이다. 그런데 b는 영인자가 아니고 c 6= 0 이므로 bc 6= 0 이 된다. 그러므로 a는 영인자가 된다. 이것은 a ∈ G_n에 모순이다.

(ii) G_n에서 곱셈에 대한 결합법칙은 Zn에서의 성질에 의해 성립한다.

(iii) 역원의 존재;

a ∈ Gn이라 하고 G_n = {1, a, a2, ·, am}이라 하자. 그러면 a · 1, a · a, a · a1, · · · , a · am

은 서로 다른 원소들이 된다. 왜냐하면 b, c ∈ G_n (b 6= c)에 대해 ab = ac 이면 ab − ac = a(b − c) = 0 이므로 a가 영인자가 되어 모순이 생긴다. 따라서 집합 {a · 1, a · a, a · a₁, · · · , a · a_m}은 G_n와 같은 집합이 되고 나아가 ab = 1이되는 b ∈ G_n 가 존재하게 된다.

(iv) Zn의 항등원 1은 영인자가 아니므로 1 ∈ G_n이다.

양의 정수 n에 대해 n과 서로소이고 n보다 작은 양의 정수들의 개수를 φ(n)으로 표기하고 오일러 파이 함수(Euler phi-function)이라 부른다. 예를 들면 φ(12) = 4, φ(15) = 8 이다. 그리고 p가 소수일 때 φ(p) = p − 1 이다. 나아가 앞서 배운 정리에 의해 φ(n)은 Zn에서 영인자가 아닌 수의 개수와 같다. 즉, φ(n) = |G_n| 이다.

Theorem 0.9. (Euler’s Theorem) n은 양의 정수이고 a는 n과 서로소인 정수일 때 a^φ(n) ≡ 1 (mod n) 이다.

Proof. a ≡ b (mod n)이 되는 b ∈ {1, 2 · · · , n − 1}가 존재한다. a와 n이 서로소이 므로 b와 n도 서로소이다. 그리고

a^φ(n) ≡ b^φ(n) (mod n) 임을 알 수 있다. b ∈ G_n이고 |G_n| = φ(n) 이므로

a^φ(n) ≡ b^φ(n) ≡ 1 (mod n) 이 된다.

<학생들이 도전할 정리 증명하기>

정수론에서 산술적인 과정을 통해 이미 배운 내용을 이제는 대수적인 원리를 이 용하여 해결할 수 있음을 익힌다.

Theorem 0.10. a ∈ Zm이고 gcd(a, m) = 1이라 하자. 이 때 각각의 b ∈ Zm에 대해 방정식 ax = b는 Zm안에서 유일한 해를 가진다.

Proof. 학생들이 해결하고 발표해 본다.

Theorem 0.11. a, b ∈ Zm이고 gcd(a, m) = d일 때 방정식 ax = b가 Zm안에서 해를 가질 필요충분조건은 d|b이다. 그리고 해를 가지는 경우에 해의 개수는 d개 이다.

Proof. 조별 문제 해결을 통해 발표하도록 한다.

<연습>

1. 다음 방정식들의 해를 구하여라.

(1) 12x ≡ 27 mod 18 (2) 15x ≡ 27 mod 18 (3) 45x ≡ 15 mod 24