1 1 n 0, 1, 2,, n n 2 a, b a n b n a, b n a b (mod n) 1 1. n = (mod 10) 2. n = (mod 9) n II Z n := {0, 1, 2,, n 1} 1.

1 1 n 0, 1, 2,, n 1 1.1 n 2 a, b a n b n a, b n a b (mod n) 1 1. n = 10 1567 237 (mod 10) 2. n = 9 1567 1826578 (mod 9) n II Z n := {0, 1, 2,, n 1} 1.2 a b a = bq + r (0 r < b) q, r q a b r 2 1. a = 456, b = 11 456 = 11 41 + 5 456 11 41, 5 2. a = 38, b = 7 38 = 7 ( 6) + 4 38 7 6, 4 1.3 a b (mod n) a b n : = a b n a =

2 1 na +r 1, b = nb +r 2 0 r 1, r 2 < n a b = n(a b )+(r 1 r 2 ) r 1 r 2 n r 1 = r 2 r 1 r 2 n t r 1 r 2 = nt 0 r 1 < n, 0 r 2 < n 0 r 1 r 2 < n t = 0 r 1 = r 2. a b (mod n) = a, b n a = na + r, b = nb + r a b = n(a b ) n 1.4 (a) a b (mod n), c d (mod n) = a ± c b ± d (mod n). (b) a b (mod n), c d (mod n) = a c b d (mod n). : (b) (a) a b (mod n) 1.2 a b n k a b = nk l c d = nl ac bd = ac bc + bc bd = (a b)c + b(c d) = nkc + bnl = n(kc + bl) ac bd n a c b d (mod n). 3 3143 68932 (mod 10) 3143 3 (mod 10), 68932 2 (mod 10) 3143 68932 2 3 = 6 (mod 10) 3143 68932 10 6 3143 68932 3. 3143 2 (mod 3), 68932 1 (mod 3) 3143 68932 3 3143 68932 2 1 (mod 3) 2 n 2 mod n {0, 1, 2,, n 1} Z n 1.5 a, b Z n 1. a, b a + b n a + n b 2. a, b a b n a n b 3. a, b a b n a n b a ± n b, a n b Z n 4 1. n = 10 3 + 10 9 = 2, 3 10 9 = 4, 3 10 9 = 7

3 2. n = 11 89 + 11 34 = 2, 36 11 52 = 6, 7 11 8 = 1 (ring) (f) Z n 1.6 (a) ) (a + n b) + n c = a + n (b + n c) (b) ) a + n b = b + n a (c) ) a + n 0 = 0 + n a = a (d) ) a + n (n a) = (n a) + n a = 0 (e) ) (a n b) n c = a n (b n c) (f) ) a n b = b n a (g) ) a n 1 = 1 n a = a (h) ) (a + n b) n c = (a n c) + (b n c) : 1 (a) (d) + group (Z n, +) (b)

4 1 1 1. 7 + 13 10 (2) 7 13 10 (3) 7 13 10 (4) 17 + 28 26 (5) 17 28 26 (6) 17 28 26 2. Z 12 a 4 12 a = 0 a a = 0, 1,, 11 ) 3. Z 16 a 6 16 a = 0 a 4. 1 + 11 2 + 11 3 + 11 4 + 11 5 + 11 6 + 11 7 + 11 8 + 11 9 + 11 10 5. (1) 1 + 10 2 + 10 3 + 10 4 + 10 5 + 10 6 + 10 7 + 10 8 + 10 9 (2) 1 + 9 2 + 9 3 + 9 4 + 9 5 + 9 6 + 9 7 + 9 8 (3) 1 + 8 2 + 8 3 + 8 4 + 8 5 + 8 6 + 8 7 6. 4 5 7. (1) 1 5 2 5 3 5 4 (2) 1 6 2 6 3 6 4 6 5 6 6 (3) 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 8. 7 )

5 2 2.1 a, d a = qd q d a a d d a 2.2 a, d d a b d a, b 2.3 a, b a = a d, b = b d d a, b a, b (greatest common divisor) gcd(a, b) (a, b) a, b 1 a, b 5 a = 18, b = 30 d d = 1, 2, 3, 6, 1, 2, 3, 6 8 6 (18, 30) = 6. 6 a = 40, b = 27 d d = 1, 1 1 (40, 27) = 1. 40 27 2.4 a, b a > b a b r : (a, b) = d, (b, r) = d (a, b) = (b, r) (i) a = bq + r d r a = da, b = db r = a bq = d(a b q) d b, r d d.

6 2 (ii) b = d b 0, r = d r 0 a = bq + r = d (b 0 q + r 0 ) d a d a, b d d (iii) d = d. 2.5( ) a, b (a > b) (a, b) r i 1 r i 1. a b q 1 r 1 a = bq 1 +r 1, (0 r 1 < b). r 0 = b 2. r 1 0 r 0 (= b) r 1 q 2 r 2 b = r 1 q 2 + r 2, (0 r 2 < r 1 ). 3. r 2 0 r 1 r 2 q 3 r 3 r 1 = r 2 q 3 + r 3, (0 r 3 < r 2 ). 4. r i 1 r i r i 1 = r i q i+1 + r i+1, (0 r i+1 < r i ). 5. r k 1 = r k q k+1 r k+1 = 0 (a, b) = r k : 1 (a, b) = (b, r 1 ) = (r 1, r 2 ) = = (r k, r k 1 ) = (r k, 0) = r k 2.6 a, b (a, b) = d ax + by = d x, y : 7 (40, 27) = 1 40x + 27y = 1 x, y 1 40 = 27 1 + 13 13 = a b 2 27 = 13 2 + 1 1 = 27 13 2 = b 2(a b) = 13 = 2a + 3b 1 = 2a + 3b x = 2, y = 3 40x + 27y = 1 8 (123456, 789) a = 123456, b = 789

7 1 123456 = 789 156 + 372 372 = a 156b 2 789 = 372 2 + 45 45 = 2a + 313b 3 372 = 45 8 + 12 12 = 17a 2660b 4 45 = 12 3 + 9 9 = 53a + 8293b 5 12 = 9 1 + 3 3 = 70a 10953b 6 9 = 3 3 + 0 0 (123456, 789) = 3 123456x + 789y = 3 (x, y) = (70, 10953) 2.7 a, b, c a bc (a, b) = 1 a c : (a, b) = 1 2.6 ax + by = 1 x, y c acx + bcy = c a bc bc = at t acx + aty = a(cx + ty) a c a 2.8 2 p p ±1, ±p 1 100 2 119 2.9 p a, b p ab p a p b : p a (p, a) = 1 2.7 p b

8 2 2 1. (1) (18, 45) (2) (182, 143) (3) (102, 84) 2. 1 x, y (1) 18x + 45y = (18, 45). (2) 182x + 143y = (182, 143). (3) 102x + 84y = (102, 84). 3. 1 12 12 1 2, 3, 4, 6 4. 13 21 5. 4 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 6. 12345 67890 (12345, 67890) 12345x + 67890y = (12345, 67890)

9 3 Z n Z n = {0, 1, 2,, n 1} + n n n Z n 2 Z n M 2 M M M M M = {(a, b) a, b M} II 1 1. G 2 : G G G G e G, x G (x e = e x = x). e G x G, y G (x y = y x = e). y x x, y, z G ((x y) z = x (y z)). 2 e 1, e 2 e 1 = e 1 e 2 = e 2 9 Z 6 : n = 6 Z 6 = {0, 1, 2, 3, 4, 5}. 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 3 Z 7 : n = 7 Z 6 = {0, 1, 2, 3, 4, 5, 6}.

10 3 Z n 0 1 2 3 4 5 6 0 1 2 3 4 5 6 Z n 2 2 2 1. R 2 : R R R : R R R R R 0 e R, x R (x e = e x = x). e x, y, z R ((x y) z = x (y z)). x, y, z R ((x y) z = (x z) (y z)). 2. R 0 x R (x 0 = y R (x y = e)); 0 R 10 R = Z n + n, n Z n (a + n b) n c = a n c + n b n c Z n n 3.1 n Z n a n (a, n) = 1 a n r = 1 r Z n : (a, n) = 1 ax + ny = 1 x, y Z 2

11 2.6 ax 1 (mod n) x n r x r (mod n) r Z n a n r = 1 3.2 n = p Z p : p 0 a = 1, 2,, p 1 p 3.1 a p x = 1 x Z p 3.3 n Z n : n 1 < a, b < n n = ab Z n a, b 0 Z n b n x = 1 x Z n a a n (b n x) = (a n b) x = 0 n x = 0 a n 1 = a a = 0 n Z n 3.4 Z n a n Z n b b n a n x = b x Z n : a n 3.1 a n y = 1 y Z n b (a n y) n b = a n (y n b) = b x = y n b 3.5 Z n n Z n a 0 n 1 Z n 1 :a n 3.1 a n y = y n a = 1 y Z n a n x 1 = a n x 2 y y n (a n x 1 ) = y n (a n x 2 ). y n (a n x 1 ) = (y n a) n x 1 = 1 n x 1 = x 1, y n (a n x 2 ) = (y n a) n x 2 = 1 n x 2 = x 2 x 1 = x 2 x = 0, 1,, n 1 a x n

12 3 Z n 3 1. Z 6 Z 6 x (1) 5 6 x = 2 (2) 3 6 x = 3 (3) x 6 4 = 2 2. Z 6 Z 6 x (1) 5 6 x) + 6 3 = 1 (2) 5 6 x) + 6 3 = (3 6 x) + 6 1 (3) (2 6 x) + 6 4 = (5 6 x) + 6 5 3. Z 11 1 10 4. 3 Z 11 x (1) 4 11 x = 3 (2) 8 11 x) + 11 7 = (5 11 x) + 11 10 (3) (2 11 x) + 11 5 = (9 11 x) + 11 3 5. Z 13 1 12 6. 5 Z 13 x (1) 6 13 x = 5 (2) 9 13 x) + 13 3 = (3 13 x) + 13 11 (3) (2 13 x) + 13 5 = (7 13 x) + 13 3 7. Z 6 0 0 2 Z n 0 0 2

13 4 1 1 2x + 5y = 1 (x, y) Z Z 2x + 5y = 1 (x, y) = ( 2, 1). 1 6x + 9y = 2 1 x, y Z 3 2 3 1 4.1 a, b, c Z ax + by = c x, y (a, b) c : (1) = (a, b) = d, a = a d, b = b d ax+by = d(a x + b y) = c a x + b y Z d c. (2) = c = dk 2 2.6 ax+by = d x, y Z a(xk) + b(yk) = dk = c xk, yk Z 1 ax + bc = c a, b d = (a, b) c c = c d ax + cy = d x, y c a(c x) + b(c y) = c d = c x 0 = c x, y 0 = c y

14 4 1 4.2 a, b, c Z, d = (a, b) c a = a d, b = b d ax+by = c x = x 0, y = y 0 x = x 0 + b t y = y 0 a t t : ax 0 +by 0 = c x, y ax+by = c 2 a(x x 0 )+b(y y 0 ) = 0 a(x x 0 ) = b(y 0 y) (a, b) = d a (x x 0 ) = b (y 0 y) a (x x 0 ) = b (y 0 y) a = a d, b = b d (a, b ) = 1 2 2.7 a y 0 y y 0 y = a t t Z y = y 0 a t. a (x x 0 ) = b a x x 0 = b t x = x 0 + b t (x 0 + b t, y 0 a t) ax + by = c a(x 0 +b t)+b(y 0 a t) = ax 0 +by 0 +ab t ba t = c+da b t db a t = c. 11 18x + 30y = 12 x = 4, y = 2 x = 4 + 5t y = 2 3t t Z t = ±1, ±2, ±3, (x, y) = (9, 5), ( 1, 1), (14, 8), ( 6, 4), (19, 11), ( 11, 7), 12 40x + 27 = 3, 40x + 27y = 1 x = 2, y = 3 3 (x, y) = ( 6, 9) x = 6 + 27t y = 9 40t

15 t Z (x, y) = (21, 31), ( 33, 49) t = ±1 (a, b) = d ax + by = d (x 0, y 0 ), ) 1 1. ax + by = c a, b, c Z 2. (a, b) = d 3. d c 4. d c (a, b) = d c a = a d, b = b d, c = dc 5. ax o + by o = d x o, y o x = c x o + b t 6. y = c y o a t (t Z) 3 ax + by = c d a x + b y = c (a, b ) = 1 a k + b m = 1 k, m x 0 = kc, y 0 = mc x = x (x 0, y 0 ) a x + b y = c 0 + b t (t Z) y = y 0 a t

16 4 1 4 1. 1 (1) 3x + 5y = 1 (2) 4x + 10y = 6 (3) 6x 15y = 9 2. 1 x 1 10 (1) 2x 7y = 3. (2) 7x 3y = 2. (3) 6x + 4y = 8. 3. 1 x, y (1) 3x + 2y = 20. (2) 5x + 3y = 35. (3) 7x + 4y = 40. 4. (1) 10 (2) 72 5. 4 (1) 1 6. 1 ax + by = 6 1 a, b 1 a b 6 b = 6 a b = 5 7. (2016 IA) 92x + 197y = 1 x, y, x x = a, y = b 92x + 197y = 10 x, y, x x = c, y = d

17 5 1 ax c (mod n) 1 1 ax c (mod n) y(ax c = ny) ax ny = c ax c (mod n) x = x o ax o c (mod n) ax o c n,ax o c = ny o y o ax o ny o = c ax ny = c (x o, y o ) d = (a, n) x = x o n d t y = y o a (t Z) x = x o n t (t Z) d t d ax c (mod n) ( x. 5.1 n a, c ax c (mod n) 1 x 1 5.2 1 ax c (mod n) x = x o x 1 x o (mod n) x 1 : x 1 x o (mod n) x 1 = x o + nt ax o c (mod n) y o (ax o ny o = c) y 1 = y o + at ax 1 ny 1 = a(x o +nt) n(y o + at) = ax o ny o +ant ant = ax o ny o = c ax 1 c (mod n) 4 1 ax c (mod n) 0 x < n

18 5 1 5.3 d = (a, n) a, n 1 ax c (mod n) d c. 0 x < b d : n = n d x 1 x = x 1, x 1 + n, x 1 + 2n,, x 1 + (d 1)n d : 1 ax c (mod n) ax c n y ax c = ny ax ny = c 1 ax c (mod n) 1 ax ny = c (a, n) c 4.1 1 ax c (mod n) (x 0, y 0 ) t d = (a, n) x = x 0 n d t = x o n t, y = y 0 a t 0 x < n d 0 x 0 n t < n x o n d < t x o n. x d : 0 x 1 x = x 1, x 1 + n, x 1 + 2n,, x 1 + (d 1)n x 0 n d < t x 0 n t x 0 x < n d 5.3 Z n (3 5.4 Z n a, c Z n a n x = c (a, n) = d c (a, n) = d c d x 1 x = x 1, x 1 + n, x 1 + 2n,, x 1 + (d 1)n 13 (a) 72x 47 (mod 200) (b) 8x 6 (mod 14) : (a) (72, 200) = 8 8 47 (b) (8, 14) = 2 0 x < 14 2 8x 14y = 6 (x, y) = ( 1, 1) x = 1 7t 1 t = 1, 2 x = 6, 13 1 y

1 1. 1 ax c (mod n) 2. d = (a, n) 3. d c 19 4. d c n = n d ax ny = c 1 x o 5. x o n r 6. x = r, r + n, r + 2n,, r + (d 1)n (mod n) 5 1. 1 (1) 3x 4 (mod 5) (2) 4x 7 (mod 9) (3) 10x 4 (mod 12) 2. 1 (1) 4x + 2 x + 6 (mod 7) (2) 8x + 2 2x 7 (mod 15) (3) 3x 4 7x 2 (mod 18) 3. 1 4x a (mod 10) 0 9 a 4. 10 10 5 1 1 4 1 13 1 1

21 6 6.1 n 2 n : n = ab 1 < a, b < n a > n, a > n n = ab > ( n) 2 = n a n b n 1. n 2. S = {2, 3, 4,, n} 3. p = 2 4. p p 5. S p p 6. p n p 4 7 7. S n 5 6.2 n n 1 6.3 : p 1, p 2,, p n N = p 1 p 2 p n + 1 6.2 N q q = N q p 1, p 2,, p n q N N p i 1

22 6 6 (Euler Ω := { } 1. n=1 1 n =. 1 2. n = n=1 (1 + 2 1 + 2 2 + 2 3 + + 2 k + ) (1 + 3 1 + 3 2 + 3 3 + + 3 k + ) (1 + 5 1 + 5 2 + 5 3 + + 5 k + ) (1 + 7 1 + 7 2 + 7 3 + + 7 k + ) (1+p 1 +p 2 +p 3 + +p k + ) = 1 1 p 1. p Ω 3. Ω 1 1 < 1 p 1 n = p Ω n=1 Ω 6.4 p 3 1. n 2 n + p n = 1, 2, 3,, p 1 2. p 2, 3, 4, 11, 17, 41 3. 2 Q( 1 4p) 1 : 2 6.5 n n = p e1 1 pe2 2 pe r r p 1, p 2,, p r e 1, e 2,, e r p 1, p 2,, p r : 7 2 Q( 5) 6 = 2 3 = (1 5)(1 + 5)

23 6 1. 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 4, 6, 8, 10 12 30 4 2. n p p s n p s+1 n v p (n) = s (1) v 2 (100) (2) v 3 (162) (3) v 5 (1234) (4) v 7 (1029) 3. 2 (1) n, m p v p (nm) = v p (n) + v p (m) (2) n, m p v p (n + m) min(v p (n), v p (m)) min(a, b) a, b

25 7 n 3 x n + y x = z n xyz 0 17 (P. Fermat) 1 n = 4 n = 3 (L. Euler) (E. Kummer) 1994 2 (A. Wiles) Z p = {0, 1, 2,, p 1} F p 1 ( 3 3.2) p F p (Field) 0 x F p (x 0 = x 1 F p ). : a F p 0 a p (a, p) = 1 2.6 x, y Z(ax + py = 1) ax 1 (mod p) x p b b F p ab = 1 b = a 1 (a) a p a p 1 1 (mod p) p a a p 1 1 p (b) a a p a (mod p) a a p a p (a ) a F p (a 0 = a p 1 = 1). (b ) a F p (a p = a). 8 (a), (b) (a ), (b ) 1 n = 1, 2 3 2 + 4 2 = 5 2 2

26 7 9 (b), (b ) (a), (a ) a p a p p a 0 (mod p) a p 0 (mod p) a p a (mod p) a p a p 1 1 (mod p) a a p a (mod p) : 2 p = 2 p p > 2 (i) a = 1, 2, a p a (mod p) a = 1 a p 1 (mod p) n p n (mod p) (n + 1) p n + 1 (mod p) 2 (n + 1) p = n p + pn p 1 p(p 1) + n p 2 + + pn + 1 2 1 p (n + 1) p n p + 1 (mod p) n p n (mod p) (n + 1) p n + 1 (mod p) a = 1, 2, 3, 4, a p a (mod p) a a = b b > 0 b p b (mod p) p a p = ( 1) p b p = b p b = a (mod p) a p ax 1 (mod p) x a p a (mod p) x a p x ax 1 (mod p) a p x = a p 1 ax a p 1 (mod p) a p 1 1 (mod p) (ii) F p = {x 1, x 2,, x p } {ax 1, ax 2,, ax p } = {x 1, x 2,, x p } ax i = ax j a 1 F p a 1 x i = x j {ax 1, ax 2,, ax p } F p p ax 1 ax 2 ax p = a p 1 x 1 x 2 x p = x 1 x 2 x p a p 1 = 1 14 2 10000 13 10000 13 1 = 12 2 12 1 (mod 13) 12 8 = 96 9600 12 400 = (96+4) 4 12, 4 10000 = 12 m+4 m 2 12 1 (mod 13) 2 10000 = 2 12 m+4 = 2 12 m 2 3 = (2 12 ) m 2 4 2 4 = 16 3 (mod 13) 3 15 3 10000 17 10000 17 1 = 16 10000 = 16 625 3 10000 = 3 16 625 =

2 12 m 2 3 = (3 16 ) 625 1 (mod 13) 1 27 7 7.1 F p 0 a a p 0 0 : a a+a+ +a = p a 0 (mod p) p a 0 < m < p m a+a+ +a = ma 0 (mod p) p ma 2.7 2.9 p a p m 7.2 F p 0 (p 1) 1 : 7.2 p a a p 1 1 (mod p) : 7.3 0 a a p 2 a : a p 1 = 1 a p 1 = a a p 2 = 1 a 1 = a p 2

28 7 7 1. (1) 2 123 7 (2) 3 3333 11 (3) 10 10000 7 2. (1) 1 2 + 2 2 + + 99 2 3 (2) 1 4 + 2 4 + + 100 4 5 (3) 1 6 + 2 6 + + 98 6 7 3. 1 10 2 10 + 3 10 4 10 + + 99 10 11 4. 3 5. 1 5 + 2 5 + + 98 5 7 6. n 1 n + 2 n + + 98 n 7 7. 6

29 8 K F p R C Q K : (field) 0 8.1 f(x) = a 0 + a 1 x + a 2 x 2 + + a n x n a i K K- (polynomial) a n 0 f(x) (degree) n deg f(x) = n 10 1 1 2 2, 3 3 f(x) = a 0 a 0 0 0 0 11 f(x) = a 0 +a 1 x+a 2 x 2 + +a n x n x x f(t) = a 0 +a 1 t+a 2 t 2 + +a n t n K- 8.2 2 K- f(x) = a 0 + a 1 x + a 2 x 2 + + a n x n, g(x) = max{n,m} b 0 + b 1 x + + b m x m f(x) + g(x) := (a i + b i )x i i=0 12 0 f(x) f(x) + 0 = 0 + f(x) = f(x)

30 8 16 F 5 - f(x) = 4x 2 + 3x + 1 g(x) = 2x + 1 f(x) + g(x) = 4x 2 + 5x + 2 = 4x 2 + 2 F 5 5 = 0 8.3 2 K- f(x) = a 0 + a 1 x + a 2 x 2 + + a n x n, g(x) = max{n,m} b 0 + b 1 x + + b m x m f(x) g(x) := (a i b i )x i i=0 17 F 5 - f(x) = 4x 2 +3x+1 g(x) = 2x+1 f(x) g(x) f(x) g(x) = 4x 2 + x g(x) f(x) = 4x 2 x = x 2 + 4x F 5 4 = 1, 1 = 4 8.4 2 K- f(x) = a 0 + a 1 x + a 2 x 2 + + a n x n, g(x) = b 0 + nm b 1 x + + b m x m f(x) g(x) = f(x) g(x) := ( a i b j )x l l=0 i+j=l 13 1 f(x) f(x) 1 = 1 f(x) = f(x) 18 F 5 - f(x) = 4x 2 + 3x + 1 g(x) = 2x + 1 f(x) g(x) = 8x 3 +4x 2 +6x 2 +3x+2x+1 = 8x 3 +10x 2 +5x+1 = 3x 3 +1 F 5 8 = 3, 10 = 0, 5 = 0 5 = 0 19 F 7 (x 2 + 3x + 5) (2x + 4) = 2x 3 + 4x 2 + 6x 2 + 12x + 10x + 20 = 2x 3 + 10x 2 + 22x + 20 = 2x 3 + 3x 2 + x + 6 F 7 10 = 3, 22 = 1, 20 = 6 5 = 0 8.5 K- K[x] 14 x t K[x] = K[t]

8.6 31 K[x] (a) ) (f(x) + g(x)) + h(x) = f(x) + (g(x) + h(x)) (b) ) f(x) + g(x) = g(x) + h(x) (c) ) f(x) + 0 = 0 + f(x) = f(x) (d) ) f(x) + ( f(x)) = ( f(x)) + f(x) = 0 (e) ) (f(x) g(x)) h(x) = f(x) (g(x) h(x)) (f) ) f(x) g(x) = g(x) f(x) (g) ) f(x) 1 = 1 f(x) = f(x) (h) ) (f(x) + g(x)) h(x) = (f(x) h(x)) + (g(x) h(x)) : 15 1.6 Z n 8.6 8.7 f(x), g(x) K[x] deg g(x) > 0 f(x) = g(x)q(x) + r(x) deg r(x) < deg g(x) q(x), r(x) K[x] q(x) f(x) g(x) r(x) f(x) g(x) 20 K = F 5 = {0, 1, 2, 3, 4} f(x) = 2x 3 + 3x 2 + 4x + 2 g(x) = 3x 2 + x + 2 q(x), r(x) mod 5 q(x) = 4x + 3, r(x) = 3x + 1

32 8 8 1. F 7 - f(x) = 4x 3 + 5x + 6, g(x) = 2x 2 + 3x + 2 (1) f(x) + g(x) (2) f(x) g(x) (3) g(x) f(x) (4) f(x) g(x) 2. (1) F 2 (x + 1) 2 (2) F 3 (x + 1) 3 (3) F 5 (x + 1) 5 3. 2 1 4. (1) F 5 3x 3 + 2x 2 + 2x + 4 4x 2 + 3x + 2 (2) F 7 5x 3 + 6x 2 + 2 3x + 4 (3) F 11 x 4 + 10 x 3 + x 2 + x + 1 5. F 5 1 (1) x 2 + 3x + 2 (2) x 2 + 4 (3) x 2 + 2x + 2

33 9 9.1 K f(x) = a 0 + a 1 x + a 2 x 2 + + a n x n a 0 + a 1 x + a 2 x 2 + + a n x n = 0 K- n (equation) f(α) = 0 α K, f(x) root 9.2 K n n : 9.3 9.3 K f(x) = 0 α f(x) f(x) = (x α)g(x) g(x) K n 1 : f(x) x α f(x) = (x α)g(x) + r r K x = α f(α) = r f(α) = 0 r = 0 f(x) = (x α)g(x) degf(x) = deg(x α) + degg(x) degg(x) = n 1 21 K = F 7 = {0, 1, 2, 3, 4, 5, 6} f(x) = 2x 2 + 4x + 5 f(x) = 0 f(α) = 0 α F 7 x F 7 f(2) = 0 f(x) x 2 f(x) = (x 2)(2x + 1) 2x + 1 = 0 F 7 x = 3 2, 3 22 K = F 23 = {0, 1, 2, 3, 4, 5, 6,, 21, 22} F 23-3 x 3 + 2x 2 + 2x + 18 = 0 f(x) = x 3 + 2x 2 + 2x + 18 f(1) = 0 f(x) x 1(= x + 22) f(x) = (x 1)(x 2 + 3x + 5) g(x) = x 2 + 3x + 5 g(3) = 0 g(x) x 3(= 2 + 20) g(x) = (x 3)(x + 6) g(x)

34 9 x = 6 = 17 x 3 + 2x 2 + 2x + 18 = 0 F 23 1, 3, 17 16 f(x) = a 0 + a 1 x + a 2 x 2 + + a n x n f(x) = g(x)h(x) 0 < deg g(x) < n, 0 < deg h(x) < n K- g, h f(x) K 23 K = F 11 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} f(x) = x 5 + 1 F 11 f(α) = 0 α F 11 f(x) = (x α)g(x) F 11 2 5 = 10 f(2) = 0 h(x) = x 2 + 3 F 11 h(x) = (x α)(x β) h(α) = 0, h(β) = 0 F 11 α h(α) = 0 9 1. F 7 - (1) x 2 + x + 1 = 0 (2) 3x 2 + 3x + 1 = 0 (3) x 3 + 2x 2 + 2x + 1 = 0 2. F 13 - (1) x 2 + 4 = 0 (2) 8x 2 + 4x + 1 = 0 (3) x 4 1 = 0 3. p F p x p 1 = 1 = (x 1)(x 2) (x (p 1)) 4. p (p 1)! 1 (mod p) 3 1 7, 8 5. F 17 2, 2 2, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8 8 1

35 10 10.1 1 n 3 α C 1 n α x n = 1 α C 1 n α n = 1, α m 1 (m = 1, 2, 3,, n 1) 1 4 x 4 = 1 µ 4 = {1, i, 1, i} i 2 = 1, i 3 = i, i 4 = 1 µ 4 = {i, i 2, i 3, i 4 } 1 4 i i 1 4 i 1 4 1 4 2 ±1 2 1 4 1 2 1 2 1 1, 1 2 ±i 4 24 1 8 x 8 = 1 µ 8 ζ = e 2πi 8 = cos 2πi 2πi + i sin 8 8 µ 8 = {ζ, ζ 2, ζ 3, ζ 4, ζ 5, ζ 6, ζ 7, ζ 8 } 1 8 ζ ζ 1 8 ±1, ±i 1 8 8 8 3, 5, 7 α = ζ 3, β = ζ 5, γ = ζ 7 1 8 8 1 8 4 4 n φ(n) := # {m; 1 m n, (n, m) = 1} 25 φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6, φ(8) = 4. 17 1 n φ(n) 10.2 p F p = {0, 1, 2,, p 1} 0 F p F p = {1, 2, 3,, p 1}. a F p ap 1 = 1 p 1 F p a x p 1 = 1

36 10 10.1 a F p an = 1 n (1 n p 1) a p = 3, 5, 7, F 3 = {1, 2} 1 2 = 1, 2 2 = 1 F 5: a a 2 a 3 a 4 1 1 1 1 2 4 3 1 3 4 2 1 4 1 4 1 F 7: a a 2 a 3 a 4 a 5 a 6 1 1 1 1 1 1 2 4 1 2 4 1 3 2 6 4 5 1 4 2 1 4 2 1 5 4 6 2 3 1 6 1 6 1 6 1 1 a p 1 = 1 a F p ap 1 = 1 1 n < p 1 n a n = 1 F 5 1, 4 F 7 1, 2, 4, 6 1 n < p 1 n a n 1 n = p 1 a n = 1 F 5 2, 3 F 7 3, 5 a n = 1 n (1 n p 1) p 1 10.2 a F p a p 1 : a F p, a 1 a k a m 1 (1 m k 1), a k = 1 k p 1 p 1 k r p 1 = kq + r (0 r < k) q r = (p 1) kq a r = a (p 1) kq = a p 1 (a k ) q = 1

10.2. 37 r 0 0 < r < k a k r = 0 k p 1 10.3 a F p a p 1 F p 10.3 p a p a p 1 1 10.4 p F p φ(n) 10.5 F p g g p 1 2 = 1(= p 1) : x = g p 1 2 x 2 = g p 1 = 1 x = ±1 g x 1 x = g p 1 2 = 1. p a F p 1 p 1 p 1 m a m 1 26 3 F 13 3 p 1 = 13 1 = 12 2, 3, 4, 6 3 2 = 9 1, 3 4 = 3 1, 3 6 = 27 = 1 3 6 4 F 13 4 p 1 = 13 1 = 12 2, 3, 4, 6 4 2 = 3 1, 4 4 = 9 1, 4 6 = 27 = 1 4 6 5 6 F 13 6 p 1 = 13 1 = 12 2, 3, 4, 6 6 2 = 10 1, 6 4 = 9 1, 6 6 = 12 = 1 1 6 12

38 10 10 1. (1) F 11 2 (2) F 13 2 (3) F 17 2 3 2. (1) 1 + 2 + 2 2 + 2 3 + + 2 100 11 (2) 1 + 2 + 2 2 + 2 3 + + 2 100 13 (3) 1 + 3 + 3 2 + 3 3 + + 3 100 17 3. 2(1) 1 4. 1 17 F 17 10 5. 4 1 1 (1) F 11 p 1 = 11 1 = 10 1, 2, 5 2 2 1, 2 5 1 2 F 11 27 F 5 2, 3 2 F 5 = {2, 2 2, 2 3, 2 4 } = {3, 3 2, 3 3, 3 4 }, F 7 3, 5 2 F 7 = {3, 3 2, 3 3, 3 4, 3 5, 3 6 } = {5, 5 2, 5 3, 5 4, 5 5, 5 6 } 18 F p 1 (cyclic group) r F p =< r > F p =< 2 > F 5 =< 3 > F 7 =< 3 > F 7 =< 5 >

39 11 p F p = {0, 1, 2,, p 1} 0 F p. a F p an = 1 n > 0 a ord(a) 11.1 F p r F p ri (0 i p 2) F p = {r 0, r, r 2, r 3,, r p 2 } r 0 = 1 : p 1 : ord(r) = p 1 1 i, j < p 1 r i = r j (j i) r i j = 1 i j p 1 1 i, j < p 1 i = j {r 0, r, r 2, r 3,, r p 2 } p 1 F p = {r 0, r, r 2, r 3,, r p 2 } 11.2 a F p a = rk k (0 k p 1) ind r (a) a F p r : 1 0 ind r (1) = 0. F 5 2, 3 2 1, 2, 3, 4 a 2 3 a 2 4 4 a 3 3 2 a 4 1 1

40 11 a 1 2 3 4 ord(a) 1 4 4 2 ind 2 (a) 0 1 3 2 ind 3 (a) 0 3 1 2 28 F 7 3, 5 2 1, 2, 3, 4, 5, 6 a 3 5 a 2 2 4 a 3 6 6 a 4 4 2 a 5 5 3 a 6 1 1 a 1 2 3 4 5 6 ord(a) 1 3 6 3 6 2 ind 3 (a) 0 2 1 4 5 3 ind 5 (a) 0 4 5 2 1 3 F p r r n = 1 n p 1 r n 1(mod p) n p 1 : n = q(p 1) + k (0 k < p 1) 1 = r n = r q(p 1) r k = (r p 1 ) q r k = r k 0 k < p 1 k = 0 ind r (a) log 11.3 F p r ind r (ab) ind r (a) + ind r (b) (mod p 1) ind r (a n ) n ind r (a) (mod p 1) : ind r (a) = m, ind r (b) = n, ind r (ab) = k r m = a, r n = b, r k = ab r k = ab = r m r n = r n+m r k (n+m) = 1 k (n + m) p 1 k n + m (mod p 1) ind r (ab) ind r (a) + ind r (b) (mod p 1)

41 19 log(ab) = log(a) + log(b) 11.4 F p r F p p 1 (p 1, ind r (a)) : (p 1, ind r (a)) = s, p 1 = sk, m = ind r (a) = sl (k, l) = 1 a = r m = r sl ord(a) = t a t = r mt = r stl = 1 t mt = slt p 1 t = k ord(a) = t = k = p 1 = s p 1 (p 1, ind r (a)). 11.5 F p - x n 1 = 0 F p 1 (n, p 1) > 1 n p 1 n 1 r p 1 = ns 1, r s, r 2s,, r (n 1)s : r F p x n 1 = 0 F p 1 (n, p 1) > 1 (n, p 1) = 1 α F p (α n = 1) = α = 1 (n, p 1) = 1 nk + (p 1)l = 1, k, l Z α = α nk+(p 1)l = (α n ) k (α p 1 ) l = 1 (n, p 1) = d > 1 x n 1 = 0 F p 1 n = dn, p 1 = dm d > 1 m < p 1 r m 1 (r m ) n = r nm = r n (p 1) = (r p 1 ) n = 1 n = 1 r m x n 1 = 0 n p 1 p 1 = ns j = 1, 2,, n 1 r js F p (xjs ) n = x jns = n j(p 1) = 1 x n 1 = 0 F p - n 7 3 1, r s, r 2s,, r (n 1)s 29 F 7 - x 3 1 = 0 p 1 = 3 2 r F 7 1, r 2, r 4 r = 3 1, 3 2 = 2, 3 4 = 4 r = 5 1, 5 2 = 4, 5 4 = 2 1, 2, 4

42 11 11 1. F p F p 0 (1) F 11 2 8 1(1) x F 11 2 ind 2 (x) ord(x) (2) F 13 2 8 1(2) x F 13 2 ind 2 (x) ord(x) 2. (1) F 11 x 5 1 = 0 (2) F 13 x 4 1 = 0 (3) F 17 x 8 1 = 0 3. 1 12 100 13 1

43 12 2 F p - 2 x n = a F p - 2 x n a = 0 2 a = 1 a F p, a 0 p = 2 a F 2, a 0 = a = 1 x n = 1 x = 1 p > 2 F p r xn = a x F p, x 0 k = ind k (x) x = r k ind r (x n ) n ind r (x) = n k ind r (r) = nk ind r (a) (mod p 1). x n = a x F p, x = r k 1 nx ind r (a) (mod p 1) X = k 1 nx ind r (a) (mod p 1) X = k x = r k x n = a nk ind r (a) = m(p 1) x n = (r k ) n = r nk = r indr(a)+m(p 1) = r indr(a) r m(p 1) = a 1 = a 1 nx ind r (a) (mod p 1) (n, p 1) ind r (a) 1 nx ind r (a) (mod p 1) (n, p 1) = d X = k 1, k 2,, k d r k 1, r k 2,, r k d x n = a F p -

44 12 2 F p - 2 x n = a F p r d = (n, p 1) ind r (a) d ind r (a) d ind r (a) 1 nx ind r (a) (mod p 1) d X = k 1, k 2,, k d r k1, r k2,, r k d x n = a F p - 30 F 7 2 x 4 = 2 F 7 3 2 = ind 3 (2) (4, 7 1) = 2 1 4x 2 (mod 6) 2 x = 2, 5 x 4 = 2 F 7 3 2 = 2, 3 5 = 5 2 5 n = 2 F p - 2 2 x 2 = a F p r (2, p 1) = 2 p > 2 ind r (a) ind r (a) ind r (a) 1 2x ind r (a) (mod p 1) 1 x = ind r(a), ±r ind r (a) 2 x 2 = a F p - 2 31 F 7 2 x 2 = 2 F 7 5 4 = ind 5 (2) 1 2x 4 (mod 6) 2 x = 2, 5 x 2 = 2 F 7 5 2 = 4, 5 5 = 3 2 3 a = 1 F p p 1 1

12.1 45 F p r ind r ( 1) = p 1 2 : r p 1 = 1 x = r p 1 2 x 2 = 1 x = ±1 r x = 1 r p 1 2 = 1. ind r ( 1) = p 1 2 12.2 p 3 F p - 2 x 2 = 1 p = 4k + 1 ±r p 1 4 x 2 = 1 F p - : x 2 = 1 x = ±1 (r p 1 2 ) 2 = r p 1 = 1 r p 1 2 = ±1 r r p 1 2 = 1 ind r ( 1) = p 1 p > 2 p = 4k + 1 2 p = 4m + 3 p 4 1, 3 ind r ( 1) = p 1 p = 4k + 1 2 12 1. (1) F 11 x 6 = 5 (2) F 13 x 8 = 3 (3) F 17 x 10 = 13 2. (1) F 11 x 2 = 3 (2) F 11 x 2 = 7 (3) F 13 x 2 = 10 3. F 13 x 2 = 1 4. 2 (1) F 11 x 2 + 2x + 4 = 0 (2) F 13 x 2 + 4x + 2 = 0 (3) F 17 x 2 + 9x + 7 = 0