, = = 7 6 = 42, =

http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/

1 1 2016.9.26, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.1 1 214 132 = 28258 2 + 1 + 4 1 + 3 + 2 = 7 6 = 42, 4 + 2 = 6 2 + 8 + 2 + 5 + 8 = 25, 2 + 5 = 7 6, 7 9 0 9 9 1/9

2 1 1 9 28258 = 2 10000 + 8 1000 + 2 100 + 5 10 + 8 = 2 9999 + 1 + 8 999 + 1 + 2 99 + 1 + 5 9 + 1 + 8 = 9 2 1111 + 8 111 + 2 11 + 5 1 + 2 + 8 + 2 + 5 + 8 28258 9 2 + 8 + 2 + 5 + 8 9 1.2 2 2016 9 30 2016 9 26 1 30 26 = 4 4 3 2016 9 26 2016 9 30 2 30 26 = 4 4 5 1 28 26 2 28 26 = 2 26 28 3 28 26 = 2 26 26 27 28 29 30 0 1 2 3 4 1 2 3 4 5 26 30 30 26 + 1 = 5 1 26

1.3. 3 26 28 1 i. 2016 9 29 2016 9 26 ii. 2016 9 26 2016 9 29 iii. 2016 10 26 2016 9 26 iv. 2016 9 9 2016 10 26 1.3 1 a, b n b = na b a a b a b a b 4 91 13 13 91 7 91 = 7 13 91 13 a = 13, b = 91, n = 7 2 i. 18 3 ii. 7 35 iii. 0 iv. 1

4 1 1 a b q 0 r < b r a = qb + r. r a b q 5 17 3 17 3 17 = 5 3 + 2 17 3 2 5. 17 = 6 3 + 1 17 3 1 6 17 = 5 3 2 17 = 5 3 + 2 1 17 = 5 3 + 2 0 3 1 17 = 5 3 3 + 2 + 3 = 5 1 3 + 2 + 3 17 = 6 3 + 1 3 a, b q, r a = qb + r i. a = 12, b = 5. ii. a = 23, b = 12.

1.4. 5 1.4 1.5 2 2 29 4 4 100 100 400 365.2422 6 1968 1968 = 492 4, 1968 = 19 100 + 68 4 0 100 68 0 4 100 1700 1700 = 425 4, 1700 = 17 100, 900 = 4 400 + 100 2000 2000 = 500 4, 2000 = 20 100, 2000 = 5 400 4 i1834 ii1960 iii2100. iv3600.

6 1 3 1 2 3 4 5 6 7 8 9 10 11 12 31 28, 29 31 30 31 30 31 31 30 31 30 31 31 1.6 2010 9 27 7 2010 10 8 9/27 9/28 9/29 30 10/1 2 3 4 5 6 7 8 9 7 10 7 7 7 9/27 7 {}}{ 9/28 9/29 9/30 10/1 2 3 4 5 6 7 8 9. 10 8 9 27 11. 11 = 1 7 + 4. 7 4 10 8 7 0 1 2 3 4 5 6

1.6. 7 9 27 9 17 17 27 = 10 = 2 7 + 4. 10 10 4 9 17 9/17 18 19 20 21 22 23 24 25 26 27 10 9 8 7 6 5 4 3 2 1 0 7 4 5 6 0 1 2 3 4 5 6 0 5 i. 2014 4 23 ii. 2014 6 30 iii. 2014 3 14 8 2020 4 14 2014 2015 2016 2017 2018 2019 2020 365 365 366 365 365 365 366 7 1 1 2 1 1 1 2 2014 4 14 261 + 365 + 366 + 365 + 365 + 365 + 105 = 2192. 2192 261 2014 104 2020 7 2192 = 313 7 + 1.

8 1 7 7 261 = 37 7 + 2, 105 = 15 7 2 + 1 + 2 + 1 + 1 + 1 + 0 = 8 = 1 7 + 1. 1 365 = 52 7 + 1, 366 = 52 7 + 2 1 1 1 2 + 7 4 14 1 6 2 6 + 2 = 8 = 1 7 + 1. 1 i. 7 ii. 7 7 iii. 7 6 i. 2036 9 26 ii. 3016 9 26 iii. 1980 iv. 1945 v.

1.7. 9 2016.9.29, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.6.1 4 9 127 321 4 127 = 4 31 + 3 321 = 4 80 + 1 128 = 4 32. 320 = 4 80 80 32 + 1 = 49 4 80 32 + 1 = 49 1 2 6 6 2 + 1 = 5 6 2 = 4 2 1.7 7 4 m, a, b q 1, q 2 0 r 1, r 2 < m { a = q1 m + r 1, b = q 2 m + r 2. r 1 = r 2 a b mod m.

10 1 a b m m a b mod m a b m 7 a b mod m. a b m 10 { 31 = 2 13 + 5, 34 = 3 13 + 5. 31 34 mod 13. 31 34 = 65 = 5 13. 8 11 i. 123, 1124. ii. 23, 54. 1.8 2 a,a, b, b m { a a mod m, b b mod m. i. a + b a + b mod m.

1.8. 11 ii. ab a b mod m. 11 2 23895257 153121423 13 23895257 + 153121426 = 177016683 = 13616667 13 + 12 23895257 153121426 = 3658875826476482 = 281451986652037 13 + 1 13 23895257 = 1838096 13 + 9 153121426 = 11778571 13 + 3 23895257 + 153121426 9 + 3 = 12 mod 13 23895257 153121426 9 3 = 27 1 mod 13 11 2 { a a mod m, b b mod m. { a a = q 1 m, b b = q 2 m. { a = q 1 m + a, b = q 2 m + b. a + b a + b = q 1 m + a + q 2 m + b = q 1 + q 2 m + a + b.

12 1 a + b a + b mod m. a b = q 1 m+aq 2 m+b = q 1 q 2 m 2 +bq 1 m+aq 2 m+ab = q 1 q 2 m+bq 1 +aq 2 m+ab. 9 ab a b mod m. i. 213 + 567 ii. 75318 3488 7 2 a a mod m a a m q 1 a = q 1 m + a a a a = q 1 m m b b mod m q 2 b = q 2 m + b a + b = q 1 + q 2 m + a + b a + b a + b mod m {}}{}{{}}{{} b a {} {{ }} }} {{ {} q 1m a q 2 m b = q 1 q 2 m 2 m = bq 1 m m = aq 2 m m ab 1.1: ab a b mod m a b ab ab a b 3 m m m ab a b mod m

1.9. 13 1.9 12 k + 1 0 n 0, n 1,, n k 9, n k 0 k + 1 a a = n 0 + n 1 10 + n 2 10 2 + + n k 10 k. a n 0 + n 1 + n 2 + + n k mod 9. 10 1 = 9 10 1 mod 9. i 10 i 1 i = 1 mod 9. n i 10 i n i 1 mod 9. a n 0 + n 1 + n 2 + + n k mod 9. 1241 = 9 137 + 8 1241 1 + 2 + 4 + 1 = 8 mod 9 8 10 i. 1234567 ii. 75318 3488 9 11 1, 2,, 9 9 148259367 9 12 a k 0 n 0, n 1,, n k 1 9, n k 1 0 a = n 0 + n 1 10 + n 2 10 2 + + n k 1 10 k 1. a n 0 n 1 + n 2 + + 1 k 1 n k 1 mod 11.

14 1 2016.10.3, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1 p a p a p 1 1 mod p 2 p p 1! 1 mod p 1.10 1 [ 1 ] a, b n b = na b a a b a b a b a Z b Z n Z s.t b = an. def. 5 d Z a, b Z def. d Z b Z d Z a Z 6 d Z a, b Z d Z def. a, b Z a, b Z a, b gcda, b 13 72 120 72, 120 72 = 2 3 3 2, 120 = 2 3 3 5. 2 2 3, 3 3 2 3 = 3 1 3, 5

1.11. 15 1 = 5 0 5 = 5 1 1. 2 3 3 = 24. 13 i. 486 63 486, 63 ii. 456 1193 456, 1193 1.11 a, b a, b 7 a, b a b a b a b 3 a, b, n Z a, b = a nb, b. a, b = d x, y Z s.t. a = dx, b = dy. a nb = dx ndy = dx ny d a nb, b a nb, b = d x, y Z s.t. a nb = d x, b = d y. a = a nb + nb = d x + nd y = d x + ny d a, b d = d d, d d d d d d = d a, b = d, a nb, b = d d d a, b = a nb, b

16 1 a,b Z a = q 1 b + r 1, 0 r 1 < b. a 1 := b, b 1 := r 1. a 1 = q 2 b 1 + r 2, 0 r 2 < b 1. a 2 := b 1, b 2 := r 2. a 2 = q 3 b 2 + r 3, 0 r 3 < b 2... b > r 1 > r 2 > 0 r n+1 = 0 a n 1 = q n b n 1 + r n, 0 r n < b n 1. a n := b n 1, b n := r n. a n = q n+1 b n. 3 a, b = a q 1 b, b = r 1, b = r 2, b 1 = = r n, b n 1 = r n. r n = a, b 14 391, 221 391 = 1 221 + 170. a = 391, b = 221, q 1 = 1, r 1 = 170 221 = 1 170 + 51. a 1 = b = 221, b 1 = r 1 = 170, r 2 = 51 170 = 3 51 + 17. a 2 = b 1 = 170, b 2 = r 2 = 51, r 3 = 17 51 = 3 17. 391, 221 = 17. 14 i. 48,36 ii. 1813,777 iii. 11753,8687 15 i. 51 119 ii. 133 209

1.12. Mathematica 17 2016.10.6, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.12 Mathematica Mathematica Windows Windows >Wolfram Mathematica 1.12.1 Mathematica > >.nb FactorInteger Shift Enter * 7 100 2 * Mod[100,7] 2 * 2x mod 7 x=0, 1, 2, 3, 4, 5, 6 * Table[Mod[2*x, 7],{x,0,6}] {0, 2, 4, 6, 1, 3, 5} * a=, 2,, Table[Mod[2*x, 7],{x,0,6}] * Print["a=", 2," ", Table[Mod[2*x, 7],{x,0,6}]] a=2 {0, 2, 4, 6, 1, 3, 5} * * Do[Print["a=",a," ",Table[Mod[a*x, 7],{x,0,6}]], {a,0,6}]

18 1 a=0 {0, 0, 0, 0, 0, 0, 0} a=1 {0, 1, 2, 3, 4, 5, 6} a=2 {0, 2, 4, 6, 1, 3, 5} a=3 {0, 3, 6, 2, 5, 1, 4} a=4 {0, 4, 1, 5, 2, 6, 3} a=5 {0, 5, 3, 1, 6, 4, 2} a=6 {0, 6, 5, 4, 3, 2, 1} 1.13 Z/NZ 8 NZ Z N NZ N NZ := {an a Z} = {, 2N, N, 0, N, 2N, }. 9 Z/NZ N N N 0, 1, 2,, N 1 Z NZ = {, kn,, 2N, N, 0, N, 2N,, kn, } N 0 0 0 kn kn 0 N a a+nz = {, a kn,, a 2N, a N, a, a+n, a+2n,, a+kn, } a a a + kn a + kn a {0, 1,, N 1, } Z/NZ Z/NZ x x Z/NZ = {0, 1, 2,, N 1}.

1.14. Z/NZ 19 10 Z/NZ Z/NZ x + y := x + y. x y := xy. 15 N = 8 Z/8Z i. 5 + 7 = 5 + 7 = 12 = 4. Z/8Z 12 4 12 = 1 8 + 4 ii. 5 5 = 5 5 = 25 = 1. Z/8Z 25 1 25 = 3 8 + 1 16 Z/13Z 0 12 i. 23 + 4 ii. 16 3 iii. 8 5 iv. 3 4 1.14 Z/NZ 16 Z/5Z 1.2: + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

20 1 1.3: 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 17 Z/6Z 18 Z/5Z Z/6Z 19 Z/NZ Z/5Z 20 Z/NZ Z/6Z

1.15. Z/NZ 21 2016.10.10, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.15 Z/NZ Z/NZ N = 0 N = 8 8 = 0 Z/8Z 26 = 2 8 = 0 26 = 3 8 + 2 = 0 3 + 2 = 2 Z/NZ Z/8Z 26 = 2, 3 = 5 26 + 3 = 2 + 5, 26 3 = 2 5 Z/NZ a = a, b = b a + b = a + b, ab = a b Z/NZ Z/13Z 2 < 7, 3 < 6 2 3 < 7 6, 6 < 42 Z/13Z 42 = 13 3 + 3 = 3 6 < 42 = 3 3 < 6

22 1 Z/NZ 1.16 11 2 1 12 17 x,y 3x + 4y = 5 x 2 + y 2 = 13 12 18 x, y = 2, 3 5x + 3y = 1 x, y = 1, 4 y 4 3 3 A B x 2 y A 1 x y 1.17 ax + by = c 14 391 221 391, 221 = 17 391x + 221y = 17. x, y Z

1.17. ax + by = c 23 14 391 1 1 221 391 = 1 221 + 170 221 = 1 0 170. 221 1 1 170 221 = 1 170 + 51 170 = 1 0 51. 170 3 1 51 170 = 3 51 + 17 51 = 1 0 17. 170 = 3 51 + 17 170 51 = 3 1 1 0 51 17 { 170 = 3 51 + 1 17 51 = 1 51 + 0 17 170 3 51 + 1 17 3 1 51 = 1 51 + 0 17 = 1 0 51 17 391, 221, 170, 51, 17 391 221 170 51 221, 170, 51, 17 391 221 = 1 1 1 0 1 1 1 0 3 1 1 0 51 17.

24 1 51 17 51 1 1 1 3 1 1 1 1 1 391 = 1 0 1 0 1 0 221. 0 1 0 1 0 1 391 17 = 1 3 1 1 1 1 221. 1 2 391 391 1 + 221 2 = 4 7 221 = 391 4 + 221 7 51 17 2 17 = 391 4 + 221 7. 391 221 391, 221 = 17 391x + 221y, x, y Z 391, 221 = 221, 170 = 170, 51 = 51, 17.. 14 391 1 1 221 221 = 1 0 170. { 391 = 1 221 + 1 170, 221 = 1 221 + 0 170. 221 1 1 170 170 = 1 0 51 { 221 = 1 170 + 1 51,. 170 = 1 171 + 0 51. 170 3 1 51 51 = 1 0 17 { 170 = 3 51 + 1 17, 51 = 1 51 + 0 17.

1.17. ax + by = c 25 ax + by = c ax + by = c i. a, b = d ii. c d iii. c d d a = da, b = db, c = dc a x + b y = c iv. a x 0 + b y 0 = 1 x 0, y 0 v. x, y = x 0 c, y 0 c vi. x, y = x 0 c + b t, y 0 c a t. t ax + by = c ax + by = c i. a, b a, b ii. ax + by = c iii. ax + by = c 4 a, b d a b ax + by = 0 a = da, b = db { x = b t y = a t, t Z

26 1 ax + by = 0 da x + db y = 0 d a x + b y = 0 d a b a b a x = b y b a, b = 1 x b x = b t, t Z a x = b y a b t = b y y = a t. x = b t, y = a t ax + by = c x = x 0, y = y 0 ax + by = c x 0, y 0 ax + by = c ax 0 + by 0 = c ax x 0 + by y 0 = 0 x x 0 = b t, y y 0 = a t x = x 0 + b t, y = y 0 a t a, b d ax + by = c d c d 19 391x + 221y = 34 391, 221 = 17 17 23x + 13y = 2

1.17. ax + by = c 27 14 391 1 1 221 221 = 1 0 170. 17 23 1 1 13 13 = 1 0 10. 13 1 1 10 10 = 1 0 3. 10 3 1 3 3 = 1 0 1 23 1 1 1 1 3 1 13 = 1 0 1 0 1 0 3 1 1 1 1 3 1 1 1 1 1 23 3 1 0 1 0 1 0 13 = 1 0 1 0 1 0 1 23 3 1 3 1 1 1 1 13 = 1 1 2 23 3 4 7 13 = 1 23 1 + 13 2 3 23 4 + 13 7 = 1 23 4 + 13 7 = 1 23 13 23x + 13y 23x + 13y = 2 2 23 4 2 + 13 7 2 = 1 2 23 8 + 13 14 = 2 x = 8, y = 14

28 1 a b c d 20 a 1 1 0 a b c d 1 = a 1 1 0 1 = 391x + 221y = 35 ad bc 0 1 ad bc d b c a 1 a 0 1 1 0 1 1 a = 0 1 1 a 391, 221 = 17 17 17 17 1723x + 13y = 35 35 17. ax + by = da x + db y = da x + b y ax + by d c d x, y = x 0, y 0 x, y = x 1, y 1 { ax1 + by 1 = c ax 0 c + by 0 c = c. ax 1 x 0 c + by 1 y 0 c = 0.

1.17. ax + by = c 29 a, b a, b = d a = da, b = db da x 1 x 0 c + db y 1 y 0 c = 0. d a x 1 x 0 c + b y 1 y 0 c = 0. a x 1 x 0 c = b y 1 y 0 c. a, b = 1 1 d a,b x 1 x 0 c b y 1 y 0 c a x 1 x 0 c = b t y 1 y 0 c = a t x 1, y 1 x 1, y 1 = x 0 c + b t, y 0 c a t. x, y = x 0 c + b t, y 0 c a t, 21 391x + 221y = 34. 14 391, 221 = 17. 17 34 17 = 391 4 + 221 7. 34 = 17 2 x, y = 8, 14. t Z, t :. 391 = 17 23, 221 = 17 13. t x, y = 8 + 13t, 14 23t.

30 1 21 i. 3x + 2y = 0 ii. 18x + 15y = 0 iii. 7x + 5y = 1. iv. 7x + 5y = 3 v. 18x + 15y = 3 vi. 18x + 15y = 2 vii. 209x + 57y = 19. viii. 209x + 57y = 17. ix. 209x + 57y = 76.

1.18. 31 2016.10.17, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.18 ax + by = 0 d = a, b, a = da, b = db { x = b t y = a t t Z { x = bt y = at t Z ax + by = 0 d > 1 22 391x + 221y = 0 391 = 17 23, 221 = 17 13, 34 = 17 2. a = 391, b = 221, d = 17, a = 23, b = 13. { x = 221t y = 391t t Z 391x + 221y = 0 391 221t + 221 391t = 391 221 221 391t = 0 { x = 13t y = 23t t Z t = 1 { x = 221t y = 391t t Z { x = 13 y = 23

32 1 { x = x0 ax + by = c y = y 0 ax + by = c x 0, y 0 d = a, b, a = da, b = db 23 { x = x1 y = y 1 ax 1 + by 1 = c ax 0 + by 0 = c ax 1 x 0 + by 1 y 0 = 0 X = x 1 x 0, Y = y 1 y 0 ax + by = 0 X = b t, Y = a t x 1 x 0 = b t, y 1 y 0 = a t { x = x0 + b t y = y 0 a t t Z 391x + 221y = 34 391 = 17 23, 221 = 17 13, 34 = 17 2. d = 17, a = 23, b = 13, c = 2. 23x + 13y = 1 x 0 = 4, y 0 = 7 { x = 8 + 13t y = 14 23t t Z

1.19. 33 1.19 22 i. 1204, 817. ii. 2747, 804. 23 i. 1204x + 817y = 83. ii. 2747x + 804y = 603. 24 a, b d = a, b, a = da, b = db a, b, d i. a = 1204, b = 817. ii. a = 2747, b = 804. 25 i. 28x + 19y = 1. ii. 2747x + 804y = 67. 26 i. 28x + 19y = 3. ii. 2747x + 804y = 268. 27 i. 28x + 19y = 0. ii. 2747x + 804y = 0. 28 i. 28x + 19y = 3. ii. 2747x + 804y = 268. 29 i. 11x + 9y = 4. ii. 1909x + 1162y = 498. iii. 13332x + 6767y = 11817.

34 1 2016.10.20, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.20 Z/NZ 1 Z/15Z 7 1 7 7x = 1. Z/15Z 13 x 7 13 = 91 = 15 6 + 1 = 1. Z/15Z 1 7 = 13 13 30 Z/15Z Z/15Z = {0, 1, 2,, 14} i. 18 ii. 1 2 iii. 4 5 N Z/NZ Z/NZ Z 1 N 0 1 = 1, 1 + 1 = 2, 1 + 1 + 1 = 3,, N {}}{ 1 + 1 + 1 + + 1 = N = 0. Z/NZ = {0, 1, 2, 3,, N 1} Z/NZ N N 0

1.21. Mathematica 35 Z/NZ Z/NZ Z/NZ a,b b a ax = b. a = 0, b 0 b a Z/NZ a 0 b a 24 Z/15Z 1 7 7x = 1. Z/15Z 7 1 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 7 0 7 14 6 13 5 12 4 11 3 10 2 9 1 8 Z/15Z 13 x 7 13 = 91 = 15 6 + 1 = 1. Z/15Z 1 7 = 13 31 Z/7Z Z/7Z = {0, 1, 2, 3, 4, 5, 6} 1 1 4. 2 4 5. 1.21 Mathematica Mathematica Windows > > Mathematica

36 1 1.21.1 Mathematica file>open new Shift Enter * 7 100 2 * Mod[100,7] 2 * 2x mod 7 x=0, 1, 2, 3, 4, 5, 6 * Table[Mod[2*x, 7],{x,0,6}] {0, 2, 4, 6, 1, 3, 5} * a=, 2,, Table[Mod[2*x, 7],{x,0,6}] * Print["a=", 2," ", Table[Mod[2*x, 7],{x,0,6}]] a=2 {0, 2, 4, 6, 1, 3, 5} * * Do[Print["a=",a," ",Table[Mod[a*x, 7],{x,0,6}]], {a,0,6}] a=0 {0, 0, 0, 0, 0, 0, 0} a=1 {0, 1, 2, 3, 4, 5, 6} a=2 {0, 2, 4, 6, 1, 3, 5} a=3 {0, 3, 6, 2, 5, 1, 4} a=4 {0, 4, 1, 5, 2, 6, 3} a=5 {0, 5, 3, 1, 6, 4, 2} a=6 {0, 6, 5, 4, 3, 2, 1}

1.22. Z/NZ 37 1.22 Z/NZ a Z/NZ, a 0 1 a ax = 1. Z/NZ a 1 1 1 24 a 25 Z/NZ a Z/NZ, a 0 1 a Z/15Z 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 0 5 10 0 5 10 0 5 10 0 5 10 0 5 10 1 5 ax = 1 Z/NZ ax 1 mod N ax 1 N ax + Ny = 1 26 Z/13Z 1 7 7x + 13y = 1

38 1 13 = 7 1 + 6 7 = 6 1 + 1 6 = 1 6. 13 7 = 1 1 1 0 1 1 1 0 6 1. 6 1 = 1 1 1 0 1 1 1 1 0 1 13 7 = 1 1 1 2 13 7. 7 2 + 13 1 = 1. 1 7 = 2. 32 Z/21Z 1 1 11. 2 1 3. 3 4 5. 33 0 Z/NZ N

1.23. 39 2016.10.24, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.22.1 Mathematica Print Print[ ], Yn Print : : :Print["HelloYn, 2+3, " end."] : Hello 5 end. Table Table[,{n, n_min, n_max}] : n_min n_max : : Table[2^n,{n,1,5}] : {2, 4, 8, 16, 32} Do Do[,{n, n_min, n_max}] : n_min n_max : : Do[Print[n," =",Prime[n]],{n,1,5}] : 1 =2 2 =3 3 =5 4 =7 5 =11 1.23 x Z/NZ x {0, 1, 2,, N 1} {0, 1, 2,, N 1}

40 1 a, b Z Z/NZ b a ax = b Z ax + Ny = b a, N = d d = 1 ax + Ny = b b Z/NZ a d > 1 d b b Z/NZ a d b Z/NZ b a b Z/NZ a 27 Z/21Z, b a = 3 11, 21 = 1 11 11x + 21y = 3 x = 6, y = 3 3 11 = 6 d > 1 b a = 2 3, 21 = 3 > 1, 3 2 3 2 Z/21Z 3 b a = 3 6, 21 = 3 > 1, 3 3 6 6x + 21y = 3 x = 4, 11, 18 Z/21Z 3 6 3 Z/21Z 6

1.24. 41 2016.10.27, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.24 1.24.1 28 18 9 a, b Z n Z b = na b a a, b, n 9, 18 Z 2 Z 18 = 2 9 18 9 29 a b q 0 r < b r a = qb + r. r a b q a r 1.25 4 4 100 100 400 4 100 + 400

42 1 7 7 1 365 365 = 7 52 + 1 1 1 7 i. ii. iii. iv. + + 7 1.26 13 m, a, b q 1, q 2 0 r 1, r 2 < m { a = q1 m + r 1, b = q 2 m + r 2. r 1 = r 2 a b mod m. a b m m a b mod m a b m

1.27. Z/N Z 43 1.26.1 a,a, b, b m { a a mod m, b b mod m. i. a + b a + b mod m. ii. ab a b mod m. 30 9 k 0 n 0, n 1,, n k 1 9, n k 1 0 k a a = n 0 + n 1 10 + n 2 10 2 + + n k 1 10 k 1. a n 0 + n 1 + n 2 + + n k 1 mod 9. 1.27 Z/N Z N Z/NZ := {0, 1, 2,, N 2, N 1} Z/NZ 1.28 Z/NZ ax + by = c.

44 1 1.28.1 a,b Z a = bq 1 + r 1, 0 r 1 < b. a 1 := b, b 1 := r 1. a 1 = b 1 q 2 + r 2, 0 r 2 < b 1. a 2 := b 1, b 2 := r 2. a 2 = b 2 q 3 + r 3, 0 r 3 < b 2... b > r 1 > r 2 > 0 r n+1 = 0 a n 1 = b n 1 q n + r n, 0 r n < b n 1. a n := b n 1, b n := r n. a n = b n q n+1. 3 a, b = a bq 1, b = r 1, b = r 2, b 1 = = r n, b n 1 = r n. r n = a, b 31 391, 221 391 = 221 1 + 170. 221 = 170 1 + 51. 170 = 51 3 + 17. 51 = 17 3. 391, 221 = 17.

1.28. 45 1.28.2 ax + by = c 14 391 1 1 221 221 = 1 0 170. { 391 = 1 221 + 1 170, 221 = 1 221 + 0 170. 221 1 1 170 170 = 1 0 51 { 221 = 1 170 + 1 51,. 170 = 1 171 + 0 51. 170 3 1 51 51 = 1 0 17 { 170 = 3 51 + 1 17, 51 = 1 51 + 0 17. 391, 221 = 221, 170 = 170, 51 = 51, 17. 391 221 51 17 = = 1 1 1 0 3 1 1 0 1 1 1 0 1 1 1 1 0 3 1 1 0 1 1 1 1 0 51 17. 1 391 221 51 0 1 0 1 0 1 391 17 = 1 3 1 1 1 1 221 51 1 2 391 17 = 4 7 221 =.. 391 1 + 221 2 391 4 + 221 7.

46 1 2 17 = 391 4 + 221 7. 391 221 391, 221 = 17 391x+221y, x, y Z ax + by = c ax + by = c i. a, b = d ii. c d iii. c d d a x + b y = c a, b = 1 iv. a x 0 + b y 0 = 1 x 0, y 0 v. c = dc x, y = x 0 c, y 0 c vi. a = da, b = db x, y = x 0 c + b t, y 0 c a t. t ax + by = da x + db y = da x + b y ax + by d c d 32 391x + 221y = 34. 14 391, 221 = 17. 17 34 17 23x + 13y = 2

1.29. Z/NZ 47 23x + 13y = 1 23 4 + 13 7 = 1 x, y = 4, 7 23x + 13y = 2 34 = 17 2 23x + 13y = 1 x, y = 4, 7 2 x, y = 8, 14. 391 = 17 23, 221 = 17 13. t x, y = 8 + 13t, 14 23t, t Z 1.29 Z/NZ 1 Z/15Z 7 7x = 1. Z/15Z 13 x 7 13 = 91 = 15 6 + 1 = 1. Z/15Z 1 7 = 13

48 1 Z/15Z 1 7 Z/15Z 7x = 1 7x 1 mod 15 7x + 15y = 1 Z/NZ 1 a Z/NZ ax = 1 ax 1 mod N ax + Ny = 1 Z/NZ 1.29.1 Z/NZ a Z/NZ, a 0 1 a ax = 1. Z/NZ a 1 1 1 a 33 Z/13Z 1 7 7x + 13y = 1 13 = 7 1 + 6 7 = 6 1 + 1 6 = 1 6.

1.30. 49 13 7 = 1 1 1 0 1 1 1 0 6 1. 6 1 = 1 1 1 0 1 1 1 1 0 1 13 7 = 1 1 1 2 13 7. 7 2 + 13 1 = 1. 1 7 = 2. Z/NZ a, N > 1 b a 1 a 1.30 34 a b a b q, r0 r < b a = qb + r a, b a a = qb + r i. a = 13, b = 5 ii. a = 26, b = 7 35 i. 0 x 10 ii. 12 x 22 iii. 50 x 50 5 36 9 4 77, 5, 22, 287, 36472

50 1 37 a = 234161, b = 88831 i. x a mod 17 x 0 x < 17 ii. y b mod 17 y 0 y < 17 iii. z a + b mod 17 z 0 z < 17 iv. w ab mod 17 w 0 w < 17 38 i. 65, 26 ii. 774, 215 39 Z/7Z Z/7Z = {0, 1, 2, 3, 4, 5, 6} i. 5 + 4 ii. 2 6 iii. 4486 9984 40 i. 119 21 119, 21 ii. { 119 = 21 5 + 14 21 = 21 119 21 = 0 21 14 iii. 119 5 1 21 21 21 = 1 0 14 14 = 1 1 1 0 14 7 119 21 = 0 0 14 7

1.30. 51 iv. 14 7 = 1 1 0 1 1 1 0 1 119 21 v. 1 1 1 0 1 5 1 1 0 1 = vi. 119x + 21y = 7 41 13x + 7y = 0 42 13x + 7y = 1 43 13x + 7y = 3, 44 13x + 7y = 3, 45 48x + 14y = 0 46 48x + 14y = 8 47 48x + 14y = 8 48 114x + 48y = 12 49 Z/5Z {0, 1, 2, 3, 4} i. 38 ii. 1 2

53 2 2016.11.14, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 2.1 A B C D i. A B 90 ii. A C iii. A D 1/2

54 2 1. : A A 2. A B B A :A B B A A B 3. A B B C A C :A B B C A C B A 7 C

2.2. 55 14 G i. a, b G ab G. ii. e G s.t. a G ea = ae = a. iii. a G b G s.t. ab = ba = e. iv. a, b, c G abc = abc. 2.2 90 1 2 4 3 1 4 4 3 3 2 2 1 2 3 1 2 4 1 3 4 1 2 2 3 3 4 4 1 4 3 1 4 2 1 3 2

56 2 1 2 3 4 1 2 3 4 1 2 3 4 1 4 3 2 1 2 3 4 2 3 4 1 1 2 3 4 2 1 4 3 1 2 3 4 3 4 1 2 1 2 3 4 3 2 1 4 1 2 3 4 4 1 2 3 1 2 3 4 4 3 2 1 : 4 3 1 2 1 2 3 4 1 4 3 2 4 3 1 2 1 4 1 2 3 4 3 2 3 4 1 2 15 34

2.2. 57 50 1. 2 3 1 4 1 2 3 4 4 3 2 1 2. 4 1 3 2 1 2 3 4 2 3 4 1 1 2 3 4, 3 2 1 4 3. 2

58 2 2016.11.17, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 2.3 1 5 1 2 3 4 5 1 2 3 4 5 1 2, 2 5 1 2 3 4 5 2 5 4 1 3 1 2 3 4 5 2 5 4 1 3

2.3. 59 n n σ, τ n S n n 1 n 1 2 3 4 1 2 3 4 σ τ 1 2 3 4 σ = 1 2 3 4 3 1 2 4 1 2 3 4 1 2 3 4, τ = 2 3 4 1 1 2 3 4 1 2 3 4 σ σ τ σ 1 1 2 3 4 1 2 3 4 σ τ 1 2 3 4 τσ τσ = 4 2 3 1 σ

60 2 σ σ 1 σ 1 2 3 4 3 2 4 1 σ = 3 1 2 4 2 1 4 3 σ1 = 3, σ2 = 1, σ3 = 2, σ4 = 4 {1, 2, 3, 4} σ τ A B C D B C A D σ = τ = τσ = 1 2 3 4 3 1 2 4 1 2 3 4 2 3 4 1 1 2 3 4 4 2 3 1 σ = τ = τσ = 1 2 3 4 3 1 2 4 1 2 3 4 2 3 4 1 1 2 3 4 4 2 3 1 D B C A σ, τ τσ A B C D σ, τ, τσ B C A D 1 2 3 4 1 2 3 4 2 3 1 4 σ 2 3 1 4 τσ A B C D B D C A τσ A B C D = τ σ A B C D = τ B C A D = D B C A

2.4. 61 2.4 1 2 3 4 2 4 1 3 1 2 4 3 1 1 2 4 3 a, b c a b c a a b c a b c = b c a = c a b a b c a c b n n 1 2 3 4 4 1 2 3 4 2 1 3 4 3, 4 1 2 1 1 2 3 4 2 1 4 3 1 2, 3 4 1 2 3 4 1 2 3 4 2 1 4 3 = 1 2 3 4 = 3 4 1 2 5 3 1 2 3 4 5 σ = 5 2 1 4 3 σ3 = 1 3 1

62 2 1 2 3 4 5 1 2 3 4 5 σ2 = 2 2 2 2 σ3 = 1 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 σ5 = 3 σ4 = 4 σ

2.5. 63 2.5 51 1 2 3 4 5 1 2 3 4 1 2 3 4 5 2 5 4 1 3 1 2 3 4 5 1 2 3 4 5 1 2 3 4 1 2 3 4 5 1 2 3 4 1 2 3 4 52 σ = 3 1 2 4, τ = 2 4 1 3 i. τσ ii. στ iii. σ 1 iv. σ 1 2 v. τ3 53 1 2 3 1. 3 1 2. 1 2 3 4 5 6 2. 5 1 6 4 2 3. 1 2 3 4 5 54 4 5 2 1 3 5 2 3 1 4, 1 4 2 5 3, 3 5 1 4 2, 1 2 3 4 5 1 2 3 4 5 1 4 3 2 5, 5 2 4 3 1 3 1 2 5 4, 1 2 3 4 5 1 2 3 4 5 3 1 2 5 4 5 2 4 3 1.

64 2 55 n S n 56 57 2 n 1 2, 2 3,..., i i + 1,..., n 1 n 58 n σ i < j σi > σj 1 i, j n i, j σ lσ 1 2 3 4 5 σ = 5 2 1 4 3 i, j 1, 2, 1, 3, 1, 4, 1, 5, 2, 3, 4, 5 σi > σj lσ = 6 1 2 3 4 5 2 5 4 1 3 59 1 2, 2 3,..., i i + 1,..., n 1 n τ n σ τσ lτσ lσ ± 1 60 σ lσ 61 σ lσ

2.6. 65 2016.11.21, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 2.6 2.6.1 1 2 3 4 4 S 4 σ = 3 1 2 4 τσ 1 2 3 4, τ = 2 4 3 1 σ τ 1 2 3 4 A B C D B C A D σ = τ = τσ = 1 2 3 4 3 1 2 4 1 2 3 4 2 4 3 1 1 2 3 4 3 2 4 1 σ = τ = τσ = 1 2 3 4 3 1 2 4 1 2 3 4 2 4 3 1 1 2 3 4 3 2 4 1 D B A C 1 2 3 4 62 4 S 4 σ = 4 3 1 2 i. στ. ii. τσ. iii. σ 2. iv. τ 1. 1 2 3 4, τ = 4 1 2 3 2.6.2 1 2 3 4 2 4 1 3 1 2 4 3 1 1 2 4 3

66 2 63 1 4 1 2 3 4 1 3 4 2 = 35 1 2 3 4 5 6 7 4 7 2 1 3 6 5 1 4 1 4 1 1 4 1 4 2 2 7 5 3 2 2 7 5 3 6 6 6 6 1 2 3 4 5 6 7 4 7 2 1 3 6 5 = 1 4 2 7 5 3 2.7 6 σ, τ S n στ = τσ

2.7. 67 k τ τk τ τk σ τk σ στk = τk στk = στk = τk = τσk = τσk l σ l τ τl = l. στl = στl = σl = τσl = τσl m σ, τ σm = τm = m στm = σm = m = σm = τσm = τσm x στx = τσx στ = τσ 7 σ, τ S n στ r = τσ r = σ r τ r 36 σ = 1 3 2 4 σ 1 3 2 4 1 σ 2 1 2 1, 3 4 3 σ 2 = 1 2 3 4 σ 3 = 1 4 2 3 σ 4 = 1 4 σ 3 = σ 1 1 3 2 4 1 1 3 2 4 1 σ 1 = 1 4 2 3

68 2 64 1 2 3 4 5 6 7 8 3 6 7 8 5 2 1 4 65 i. 1 4 1 3 2. ii. 2 3 1 4 2 5 2 3. iii. 1 2 3 4 2. iv. 4 2 3 1 1. 66 n n 1 2, 2 3,, k 1 k,, n 1 n 2.8 17 17 1. Joker K, Q, J, A 17 2. 1 2 3 4 5 6 7 8 Joker K Q J A K Q J 9 10 11 12 13 14 15 16 17 A K Q J A K Q J A 3. 8 9

2.8. 17 69 Joker K Q J A K Q J A K Q J A K Q J A 67 1. 1 2. 1 3. 2 4.

70 2 2016.11.24, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 2.9 0 37 a, b 1 ax = b a x = b a a 0 a 0 a a = 0 a 0 [a 0 ] x = b a. [a = 0 ] a = 0 0x = b 0 = b b b = 0 b 0 [b = 0 ] ax = b 0 = 0 x x = t, t :. [b 0 ] ax = b 0 = b 0

2.10. 71 2.10 15 G i. a, b G ab G. ii. e G s.t. a G ea = ae = a. iii. a G b G s.t. ab = ba = e. iv. a, b, c G abc = abc. G G 17 A a B b S a b a, b a b + 38 A = B = S = Z a, b Z a + b + a, b 39 σ, τ S n τσ S n S n σ, τ τσ G a, b G a b G G, a, b G ab G G, G 40 0 R := R \ {0} = {x R x 0} R R, 41 Z Z + Z, +

72 2 2.11 18 G a, b G ab = ba. a b G a, b G, ab = ba. G G G + + 42 R 2 M 2 R M 2 R, + M 2 R, + 68 M 2 R, + 43 R 2 GL 2 R 19 n n G a G, n N a n a n := n {}}{ aa a. a n a n := a 1 n. G a G, n N a n na := n {}}{ a + a + + a. a n na := n a. n n

2.12. 73 44 G e e G, 1, 1 G G G e, e G ii e = ee = e. e ii e ii 69 iii 2.12 20 G G G G #G G G G #G = G =. G 45 8 8 70 2.13 12 60 12 60 21 G a 1, a 2,, a n G G a 1, a 2,, a n a G, a = b e1 1 be2 2 ber r,

74 2 b 1, b 2, b r {a 1, a 2,, a n }, e 1, e 2,, e r Z. G a 1, a 2,, a n a 1 a 5 2a 3 1 G = a 1, a 2,, a n. {a 1, a 2,, a n } G 46 Z, + 1 Z Z = 1. n Z n = n 1 + e i e i 1 47 n S n S n = 1 2, 2 3,..., i i + 1,..., n 1 n. n 1 2, 2 3,..., i i+1,..., n 1 n 48 n 1 n σ = 12 k n, τ = 2 n3 n 1 k n k + 2. σ τ 1 n 2 D n D n = σ, τ.

2.14. 75 2.14 G G G G G G G 22 H G i. H G ii. H G 49 G G G {e G } G 50 G a G a G 51 n S n A n A n S n A n n 23 G a G G a 52 k k. 8 G e G G a G n a n = e G N S = {a 1, a 2, a 3,, a k,, a N+1 } i, j a i = a j

76 2 S G S G S N + 1 G a a 1 a i a 1 j = a j a 1 j a i j = e n = i j 2.14.1 9 σ, τ S n στ σ τ στ r = 1 n r στ r = σ r τ r σ r = τ r = 1 n r σ τ 53 σ 1 2 3 4 5 σ = 4 5 2 1 3. σ σ = 1 4 2 5 3 1 4 2 2 5 3 3 2, 3 σ 2 3 6 71 M 2 R 2 M 2 R, + 72 M 2 R GL 2 R 73 n S n

2.14. 77 74 n 1 n σ = 12 k n, τ = 2 n3 n 1 k n k + 2. e i. σ n = e. ii. τ 2 = e. iii. τστ = σ 1. 75 n 2 D n D n 76 τ n σ τσ lτσ lσ ± 1 77 n σ σ sgn σ. { 1 σ sgn σ = 1 σ 78 n A n n S n 79 G G 80 n n 1 µ n µ n 81 1 2 3 4 5 6 7 τ = 7 4 1 5 2 3 6.

79 3 2016.12.1, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 3.1 24 [ ] Z Z 54 Z Z 55 N N 2, 5 N, 2 5 = 3 N. 56 Q[x] Q[x] 25 F field i. F ii. 0 F 57 Q 58 R 59 C

80 3 3.2 0 1 3.2.1 a N x + a = 0. x = a a Z a 0, b Z ax = b. b a a n, a n 1,, a 0 Q, a n 0 a n x n + a n 1 x n 1 + + a 0 = 0. a x + a x x + a a ax x ax a 0, a 1,, a n a n x n + a n 1 x n 1 + + a 0 x 3.2.2

3.2. 81 0 0 0 0 0 0 3.2.3 x + 3 = 5. x x = 2 x + 3 = 0. x = 3 a x + a = 0. x = a Z Z

82 3 3.2.4 0 0 0 Z {0} := {a Z a 0}. a Z {0}, b Z ax = b. b a S T S S S T := {s S s T }. S T S T S = Z, T = {0} S T = Z {0} 0 3 5 = 6 10 = 9 15. Q a, b Z ax = b a Q a 0 a a 1 a Q Q

3.2. 83 3.2.5 Q Q Q a n, a n 1,, a 0 Q, a n 0 a n x n + a n 1 x n 1 + + a 0 = 0. Q Q 60 x 2 2 = 0. x = ± 2 3.2.6 3.2.7 x 2 + 1 = 0. i = 1 C := {a + bi a, b R}. 3.2.8 Z/N Z Z/NZ N 0 p Z/pZ F p N 0

84 3 2016.12.5, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 3.3 26 R R [ ] R + [ ] x, y R xy R [ ] x, y, z R xyz = xyz. [ ] x, y, z R xy + z = xy + xz, x + yz = xz + yz. R [ ] x, y R xy = yx. R + R + x, y R x + y = y + x. + 61 Z Z Z 1 2 Z

3.4. 85 62 R x R[x] := {a 0 + a 1 x + a 2 x 2 + + a k x k + + a n x n a k R, n N}. R 1 R[x] 63 R { } a11 a M 2 R := 12 a 21 a a 11, a 12, a 21, a 22 R 22 R 2 M 2 R R = Z A = AB = BA = 1 0 0 0 1 0 0 0 0 1 0 0 AB BA., B = 0 1 0 0 1 0 0 0 0 1 0 0 = = M 2 Z 0 1 0 0 0 0 0 0.. 64 Z/NZ Z/NZ N = 6 2 Z/6Z 3.4 27 R R R R + R R R R

86 3 R + R R + R R + R 65 F F + = F. F F ax = 1. F a F F a 0 F F = {a F a 0}. 66 Z Z ax = 1. Z a Z a > 1 a x = 1 0 < x < 1 x Z a = ±1 Z Z = {±1}. 67 Z/pZ p Z/pZ a x = 1. Z/pZ a Z/pZ ax 1 mod p. ax + py = 1. a, p = 1.

3.4. 87 p a 0. Z/pZ = {a Z/pZ a 0} = {1, 2,, p 1}. p Z/pZ 82 Z/6Z Z/6Z 68 Z/pZ Z/pZ Z/7Z Z/7Z = {1, 2, 3, 4, 5, 6} 3 3 1 = 3, 3 2 = 6, 3 3 = 2, 3 4 = 5, 3 5 = 1, 3 6 = 4 1 2 3 4 5 6 3 6 2 5 1 4 S 6 1 2 3 4 5 6 3 6 2 5 1 4 = 1 3 2 6 4 5 Z/7Z 3 Z/7Z = 3. p a Z/pZ Z/pZ = a. Z/pZ G n a G G 68 3 Z/7Z 1 2 3 4 5 6 3 6 2 5 1 4 S 6 6 Z/7Z 6 S 6 n S n n

88 3 3.5 69 4x + 8 = 3 x 4 8 8 8 8 4x + 8 + 8 = 3 + 8 8 8 8 8 4x = 5 4 4 1 4 1 4 4x = 1 4 5 4 1 4 1 4 4 ax + b = c b a a, b R b a R R R R R 0 R R R

3.6. 89 2016.12.8, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 3.6 3.6.1 G e G a G a k = e k a n G G n a G a n = e n k a k = e 3.6.2 R R R R := {a R a } 70 Q = {a Q a 0}. R = {a R a 0}. C = {a C a 0}. Z = {±1}. N Z/NZ := {a Z/NZ x Z/NZ s.t. ax 1 mod N}. Q, R, C 0

90 3 3.7 3.8 A P P A 3.8.1 i. A ii. P iii. A P iv. P P ε-δ 71 R R := R \ {0} = {x R x 0}. R

3.8. 91 i. A R ii. P. P G i. a, b G ab G. ii. e G s.t. a G ea = ae = a. iii. a G b G s.t. ab = ba = e. iv. a, b, c G abc = abc. R R R R R 0 R iv i R 0 ii e G s.t. e e e R iii a R a 1 a 1 R i R a, b R = ab R. a, b R, a 0, b 0 ab 0 a, b R = ab R. i ii 1 0, 1 R 1 R. 1 R a R, a 1 = 1 a = a. ii

92 3 iii a R a 0 1 a 1 a R 1 a a a R, a 1 a = 1 a a = 1. iii iv R R iv R R 3.9 A P F n n F F S P S P A S A P 83 F F := F \ {0} = {x F x 0}. F 84 N NZ Z 85 Z/NZ = {a Z/NZ ax = 1 }. Z/NZ

3.10. 93 86 p Z/pZ 87 Z/17Z Z/17Z {0, 1, 2, 3,, 15, 16} 88 Z/15Z Z/15Z {0, 1, 2, 3,, 13, 14} 3.9.1 Z/NZ Z/NZ a, b Z/NZ a 1, b 1 Z/NZ ab b 1 a 1 Z/NZ abb 1 a 1 = abb 1 a 1 = a 1 a 1 = aa 1 = 1 ab Z/NZ. 1 Z/NZ 1 1 = 1 1 Z/NZ a Z/NZ a 1 Z/NZ aa 1 = a 1 a = 1 a 1 Z/NZ a 1 Z/NZ. Z/NZ Z/NZ a Z/NZ ax + Ny = 1 a a, N = 1 3.10 4 p a p a p 1 1 mod p.

94 3 3.11 2 10 = 1024 1 mod 11. p a p a p 1 1 mod p. p 1 G G G e G a G 3.14 a G = e. G = Z/pZ 72 2 1000 mod 17 17 2 17 1 2 16 1 mod 17 1000 = 16 62 + 8 2 1000 2 16 62+8 2 16 62 2 8 1 62 2 8 = 2 8 = 256 1 mod 17 2 4 = 16 1 mod 17

3.12. 95 3.12 89 131 2 400 mod 131 {0, 1, 2,, 130} 3.13 G G H H G G G 5 G p G p G 73 43252003274489856000 = 2 27 3 14 5 3 7 2 11. Sylow 7 11 7 11 3.14 28 G H G a, b G H h H s.t. b = ah. H a ah ah := {x G x = ah h H}. ah H a 90 3 S 3 H = {1 3, 1 2 3, 1 3 2} H

96 3 10 G H G a, b G { ah = bh ah bh =. x bh x ah bh h H x = bh ah h H x = ah bh = ah. H h h 1 bhh 1 = b = ah h 1 H h h 1 H b ah bh = ahh = ah. bh ah ah = bh ah bh ah bh = 11 G H G a G H ah H H f : H ah h ah h, h H ah = ah a 1 h = a 1 ah = a 1 ah = h

3.14. 97 f ah ah fh = ah f f H, ah H ah 6 G H G G : H G H G = H G : H. a 1 H, a 2 H,, a g:h H G a i H a j H =, i j, G = a 1 H a 2 H a g:h H. a i H H G = H G : H. 1 G H G H H G G H G 91 G a G a f e G a f = e.

98 3 1 G a G a G = e. G a G a a G a G G = k a. a G = a k a = a a k = e k = e. 2 p G = Z/pZ a G a p 1 = 1. Z/pZ p 1 3.15 Z/pqZ 2 p, q Z/pqZ p 1q 1. Z/pqZ = {a Z/pqZ x Z/pqZ s.t. ax = 1} a Z/pqZ a, pq = 1 a, p = 1 a, q = 1 {0, 1, 2,, pq 1} p q Z/pqZ p 0 p = 0, 1 p = p, 2 p = 2p,, q 1 p = q 1p

3.16. 99 q q 0 q = 0, 1 q = q, 2 q = 2q,, p 1 q = p 1q p 0 Z/pqZ 74 pq p q + 1 = p 1q 1. 2 1012 mod 35 35 35 = 5 7 2 Z/35Z Z/35Z = 5 17 1 = 24 1 2 24 1 mod 35 1012 = 24 42 + 4 2 1012 2 24 42+4 2 24 42 2 4 1 42 2 4 = 2 4 = 16 mod 35 92 167 221 Z/167 221Z 93 p n Z/p n Z p n p n 1 3.16 4 4 11

100 3 2016.12.12, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 3.17 3.17.1 2 2 x 2 + ax + b = 0 x = α, β x 2 + ax + b = x αx β = x 2 α + βx + αβ = 0 { α + β = a αβ = b α + β, αβ 2 α β x 2 +ax+b = x 2 α+βx+αβ = x αx β = x βx α = x 2 β+αx+βα 2 α + β = a, αβ = b α, β x = α, β, γ 3 x 3 +ax 2 +bx+c = x αx βx γ = x 3 α+β+γx 2 +αβ+αγ+βγx αβγ = 0 α + β + γ = a αβ + αγ + βγ = b αβγ = c α, β γ

3.17. 101 3.17.2 2 2 x, y fx, y fx, y x y y x fy, x fx, y = fy, x fx, y 2 75 2 fx, y = x + y fx, y = xy fx, y = x y 2 fx, y = x y fy, x = y x = fx, y 76 2 x 2 + ax + b = x αx β = 0 { α + β = a, αβ = b. a, b α, β 94 2 2 i. x 2 + y 2 ii. x + y 2 iii. x 2 y 2 iv. x + 2y 3 + 2x + y 3

102 3 3.18 29 n x 1, x 1,, x n fx 1, x 2,, x n n S n σ σfx 1, x 2,, x n := fx σ1, x σ2,, x σn. 77 fx 1, x 2, x 3 = x 2 1 + 5x 1 x 3 4x 2 x 3 σ = 1 2 3 2 3 1 σfx 1, x 2, x 3 = fx σ1, x σ2, x σ3 = fx 2, x 3, x 1 = x 2 2+5x 2 x 1 4x 3 x 1. n S n S n 30 n fx 1, x 2,, x n n σ S n σfx 1, x 2,, x n = fx 1, x 2,, x n. n S n fx 1, x 2,, x n S n i i + 1 S n i = 1, 2,, n 1 S n S n n! i i + 1 n 1 95 3 3 i. x + y + z ii. xy + xz + yz iii. xyz iv. x 2 y + y 2 z + z 2 x

3.18. 103 31 n x 1, x 2,, x n σ k k σ 1 = x 1 + x 2 + + x n. σ 2 = x 1 x 2 + x 1 x 3 + + x i x j + + x n 1 x n, i < j. σ k = {x 1, x 2,, x n k } σ n = x 1 x 2 x n. 78 3 σ 1 = x 1 + x 2 + x 3. σ 2 = x 1 x 2 + x 1 x 3 + x 2 x 3. σ 3 = x 1 x 2 x 3. σ k 3 σ 1 = x + y + z 4 σ 1 = x + y + z + w n x + x 1 x + x 2 x + x n = x n + σ 1 x n 1 + σ 2 x n 2 + + σ n. x x 1 x x 2 x x n = x n σ 1 x n 1 + σ 2 x n 2 + + 1 n σ n. 96 x, y, z, w 4

104 3 2016.12.15, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 3.19 2 2 x 2 + ax + b = x αx β = 0 { α + β = a, αβ = b. a, b α, β 2 α, β x 2 + 5x + 3 = 0 α 2, β 2 2 x 2 α 2 + β 2 x + α 2 β 2 = 0. α, β α, β α 2 + β 2 = α + β 2 2αβ = 5 2 2 3 = 25 6 = 19. α 2 β 2 = αβ 2 = 3 2 = 9 x 2 19x + 9 = 0.

3.19. 2 105 α 2, β 2 α, β = 5 ± 5 2 4 3 = 5 ± 13 2 2 α 2 5 + 2 13 = = 52 + 2 5 13 + 13 2 2 4 β 2 5 2 13 == = 52 2 5 13 + 13 2 2 4 α 2 + β 2 = 19 5 13 + 19 + 5 13 = 19. 2 2 α 2 β 2 19 5 2 13 = 19 + 5 13 = 9. 2 2 = 19 5 13 2 = 19 + 5 13 2 n 97 2 x 2 3x 1 = 0 α, β 1 α, 1 β 2 3 n n 79 x 3 + y 3 = x + y 3 3x + yxy = σ 3 1 3σ 1 σ 2. x 3 1 + x 3 2 + x 3 3 = x 1 + x 2 + x 3 3 3x 1 + x 2 + x 3 x 1 x 2 + x 2 x 3 + x 3 x 1 + 3x 1 x 2 x 3 = σ 3 1 3σ 1 σ 2 + 3σ 3. 80 x 2 + 5x + 3 = 0 α, β α β 2 σ 1 = α + β = 5, σ 2 = αβ = 3 α β 2 = α + β 2 4αβ = 5 2 4 3 = 13

106 3 3.19.1 2 32 2 2 x, y x i y j i+j 81 i. x 3 y 2 3 + 2 = 5 ii. x 4, x 3 y, x 2 y 2, xy 3, y 4 4. 82 fx, y = x 3 y 2 + x 2 y 3 + x 3 + y 3 + 2x 2 y + 2xy 2 + 3xy. x 3 y 2, x 2 y 3 2 x 3 y 2 x 3 y 2 5 5 2xy 2 x + y = 1 + 2 = 3 3xy x + y = 1 + 1 = 2 x 3 y 2, x 2 y 3 2 5 x + y 5, x + y 3 xy, x + yxy 2 3 5 3 5 p, q, r x 3 y 2 + x 2 y 3 = px + y 5 + qx + y 3 xy + rx + yxy 2 p = 0, q = 0, r = 1 x + y 5 x 5 x + y 3 xy x 4 y fx, y x + yxy 2 = x 3 + y 3 + 2x 2 y + 2xy 2 + 3xy. 3 3 x + y 3, x + yxy

3.19. 2 107 s, t x 3 + y 3 + 2x 2 y + 2xy 2 = sx + y 3 + tx + yxy s = 1, t = 1. 3 fx, y x + yxy 2 x + y 3 + x + yxy = 3xy. 1 0 fx, y x + yxy 2 x + y 3 + x + yxy 3xy = 0. fx, y fx, y = x+yxy 2 +x+y 3 x+yxy+3xy = σ 1 σ 2 2 +σ 3 1 σ 1 σ 2 +3σ 2. i. fx, y ii. iii. iv. v. 83 fx 1, x 2, x 3 = x 2 1 + x 2 2 + x 2 3 σ 1 = x 1 + x 2 + x 3 σ 2 = x 1 x 2 + x 2 x 3 + x 3 x 1 σ 3 = x 1 x 2 x 3 x 2 1 + x 2 2 + x 2 3 = aσ 2 1 + bσ 2. x 1, x 2, x 3 = 1, 0, 0 1 = f1, 0, 0 = aσ 1 1, 0, 0 2 + bσ 2 1, 0, 0 = a. x 1, x 2, x 3 = 1, 1, 0 2 = f1, 1, 0 = aσ 1 1, 1, 0 2 + bσ 2 1, 1, 0 = 4a + b. a = 1, b = 2 x 2 1 + x 2 2 + x 2 3 = σ 2 1 2σ 2.

108 3 98 x, y, z σ 1, σ 2, σ 3 x, y, z 99 x, y, z σ 1, σ 2, σ 3 i. x 2 + y 2 + z 2 ii. x 2 y + y 2 z + z 2 x + x 2 z + y 2 x + z 2 y iii. x y 2 + y z 2 + z x 2 3.20 i. fx, y ii. iii. iv. v. n n = 3 3=1+1+1 3=1+2 3=3 3 3

3.20. 109 σ 1 = x + y + z 3 fx, y, z = x 3 +y 3 +z 3 σ 2 = xy + xz + yz σ 3 = xyz fx, y, z 3 σ 1, σ 2, σ 3 3 3 σ 1, σ 2, σ 3 1 2 3 3 3 1 + 1 + 1 σ 3 1 1 + 2 σ 1 σ 2 3 σ 3 a, b, c fx, y, z = x 3 + y 3 + z 3 = aσ 3 1 + bσ 1 σ 2 + cσ 3 [ ] aσ 3 1 + bσ 1 σ 2 + cσ 3 x, y, z a, b, c a, b, c x 3 + y 3 + z 3 =aσ 3 1 + bσ 1 σ 2 + cσ 3 =ax + y + z 3 + bx + y + zxy + xz + yz + cxyz =ax 3 + y 3 + z 3 + 3x 2 y + 3x 2 z + 3y 2 z + 3xy 2 + 3xz 2 + 3yz 2 + 6xyz + bx 2 y + x 2 z + y 2 z + xy 2 + xz 2 + yz 2 + 3xyz + cxyz =ax 3 + y 3 + z 3 + 3a + bx 2 y + x 2 z + y 2 z + xy 2 + xz 2 + yz 2 + 6a + 3b + cxyz a = 1 3a + b = 0 6a + 3b + c = 0

110 3 a = 1 b = 3 c = 3 x 3 + y 3 + z 3 = σ 3 1 3σ 1 σ 2 + 3σ 3 [ ] x 3 + y 3 + z 3 = aσ 3 1 + bσ 1 σ 2 + cσ 3 x, y, z a, b, c σ 1, σ 2, σ 3 0 x, y, z x, y, z = 1, 0, 0. σ 2 = σ 3 = 0 σ 1 = x + y + z = 1 + 0 + 0 = 1 σ 2 = xy + xz + yz = 1 0 + 1 0 + 0 0 = 0 σ 3 = xyz = 1 0 0 = 0 f1, 0, 0 = 1 3 + 0 3 + 0 3 = 1 aσ1 3 + bσ 1 σ 2 + cσ 3 1, 0, 0 = a 1 3 + b 0 0 + c 0 = a a = 1 x, y, z = 1, 1, 0. σ 3 = 0 σ 1 = 1 + 1 + 0 = 2 σ 2 = 1 1 + 1 0 + 0 0 = 1 σ 3 = 1 1 0 = 0 f1, 1, 0 = 1 3 + 1 3 + 0 3 = 2 a = 1. σ1 3 + bσ 1 σ 2 + cσ 3 1, 1, 0 = 2 3 + b 2 1 + c 0 = 8 + 2b 8 + 2b = 2 b = 3

3.20. 111 x, y, z = 1, 1, 1. σ 1, σ 2, σ 3 0 σ 1 = 1 + 1 1 = 1 σ 2 = 1 1 + 1 1 + 1 1 = 1 σ 3 = 1 1 1 = 1 f1, 1, 1 = 1 3 + 1 3 + 1 3 = 1 a = 1, b = 3. σ1 3 3σ 1 σ 2 + cσ 3 1, 1, 1 = 1 3 3 1 1 + c 1 = 4 c 4 c = 1 c = 3 x 3 + y 3 + z 3 = σ1 3 3σ 1 σ 2 + 3σ 3. x, y, z σ 1, σ 2, σ 3 0

112 3 2016.12.19, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 3.20.1 100 σ 1 = x + y, σ 2 = xy σ 1 σ 2 i. x 4 + y 4 ii. x 5 + y 5 3.20.2 2 84 2 α, β 1 { α + β = A α β = B α = A + B 2 2 β = A B 2 x 2 + bx + c = 0 α, β α + β = a α β α β a, b 2 α β 2 α β 2 = α + β 2 4αβ = b 2 4c

3.20. 113 α β = ± b 2 4c α, β = b ± b 2 4c 2 α β 1 2 α β 2 α β 3.20.3 3 33 n fx 1, x 2,, x n i j fx 1, x 2,, iˆx j,, jˆx i,, x n = fx 1, x 2,, x n. 85 2 x 1 x 2 3 x 1 x 2 x 1 x 3 x 2 x 3 n i x j i<jx 12

114 3 101 1 1 1 a 1 a 2 a n a 2 1 a 2 2 a 2 n.... a n 1 1 a n 1 2 a n 1 n 102 ω 2 + ω + 1 = 0 x 1 + ωx 2 + ω 2 x 3 3 + x 2 + ωx 1 + ω 2 x 3 3

115 4 3 2016.12.22, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 4.1 103 σ 1 = x + y, σ 2 = xy σ 1, σ 2 i. x 2 + y 2 + 4xy ii. x y 4 iii. xx + 2y 2 + y2x + y 2 104 σ 1 = x + y + z, σ 2 = xy + xz + yz, σ 3 = xyz σ 1, σ 2, σ 3 i. x 2 + y 2 + z 2 ii. x 3 + y 3 + z 3 iii. x y 4 + y z 4 + z x 4 4.2 2 2 x 2 = x 2 = 9 x = ±3. 9 = 3 2 a a 2 x 2 = 5 x = ± 5. 5 2 5 5 x + 2 x + 7 2 = 5 x = 7 ± 5. x 2 = x 1 x 2 + 4x 1 = 0. x + 2 2 = 5 x = 2 ± 5.

116 4 3 4.3 3 4.3.1 1 3 ω 1 3 ω ω 3 = 1, ω 1 2 1 ω ω ω 3 = 1 ω 3 1 = ω 1ω 2 + ω + 1 = 0 ω 1 x 2 + x + 1 = 0 2 ω, ω 2 = 1 ± 3i 2 ω ω 2 1 3 3 x 3 = a x = 3 a 1 3 ω x = 3 a, ω 3 a, ω 2 3 a ω 3 = 1 4.3.2 3 3 x 3 + ax 2 + bx + c = 0. x = t a 3 t 3 + pt + q = 0.

4.3. 3 117 3 3 t = α, β, γ x 3 + ax 2 + bx + c = 0. x = α a 3, β a 3, γ a 3 3 2 0 2 0 0 x 3 + ax 2 + bx + c = 0 x = t a 3 t3 + pt + q = 0 t 3 + pt + q = t = 0 q = a 3 + a a 3 3 t 3t 2 + p = 3 t a 3 t = 0 p = 3 a 3 t a 3 + a t a 2 + b t a + c 3 3 3 2 + 2a a 3 2 + b a 3 + c 2 + 2a t a + b 3 + b

118 4 3 86 3 x 3 6x 2 + x + 5 = 0. t 3 + pt + q = 0 x 3 6x 2 + x + 5 = 0.a = 6 6 x = t = t + 2 3 t 3 + pt + q = t + 2 3 6t + 2 2 + t + 2 + 5 t = 0 q = 2 3 6 2 2 + 2 + 5 = 8 24 + 2 + 5 = 9. t 3t 2 + p = 3t + 2 2 12t + 2 + 1. t = 0 p = 3 2 2 12 2 + 1 = 12 24 + 1 = 11. t 3 11t 9 = 0. 105 3 x 3 + 3x 2 7x + 1 = 0 t 3 + pt + q = 0 4.4 3 87 3 x 3 6x + 4 = 0 α = 3 2 + 2i + 3 2 2i, i = 1

4.4. 3 119 α = u + v x = u + v u + v 3 6u + v + 4 = 0. u 3 + v 3 + 4 + 3u + vuv 2 = 0. u + v = α uv uv = β t 2 αt + β = 0 t = u, v uv 2 = 0 u 3 + v 3 + 4 = 0 u 3 v 3 = uv 3 = 2 3 = 8 u 3 + v 3 = 4, u 3 v 3 = 8 u 3, v 3 2 T 2 + 4T + 8 = 0. T = 2 ± 2 2 8 = 2 ± 2i. u, v 3 uv = 2 u = 3 2 + 2i, v = 3 2 2i. u = ω 3 2 + 2i, v = ω 2 3 2 2i. u = ω 2 3 2 + 2i, v = ω 3 2 2i. ω 3 = 1, ω 1. x = 3 2 + 2i + 3 2 2i, x = ω 3 2 + 2i + ω 2 3 2 2i. x = ω 2 3 2 + 2i + ω 3 2 2i.

120 4 3 2016.12.26, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 4.5 2 0 x 3 + px + q = 0. 3 x 3 + ax 2 + bx + c = 0. 3 x 3 + ax 2 + bx + c = 0. x = t 1 3 a t 1 3 3 a + a t 1 2 3 a + b t 13 a + c = 0. t 3 + a2 2a 3 3 + b t + 27 ab 3 + c = 0. 2 p = a2 3 + b q = 2a3 27 ab 3 + c t 3 + pt + q = 0. α, β, γ x 3 + ax 2 + bx + c = 0.

4.5. 121 α 1 3 a, β 1 3 a, γ 1 3 a t = x + 1 3 a. x 3 + px + q = 0 u, v u + v u + v = α { uv uv = β u + v = α u, v uv = β t 2 αt + β = 0 u, v 3 x 3 + px + q = 0. x = u + v uv uv x 3 + px + q = 0 x = u + v u + v 3 + pu + v + q = 0. u 3 + v 3 + q + u + v3uv + p = 0. 3uv + p 0 uv uv 3uv = p. uv u 3 + v 3 + q = 0 u 3 v 3 u 3 v 3 = p3 27 u 3 + v 3 = q.

122 4 3 u 3, v 3 2 T 2 + qt p3 27 = 0. T = q ± 2 q 3 + s = q 3 t = q 2 + 4 27 p3. q 2 + 4 2 q 2 + 4 2 27 p3 27 p3,. u, v 3 3uv = p u = s, v = t. u = ωs, v = ω 2 t. u = ω 2 s, v = ωt. ω 3 = 1, ω 1. x = s + t, x = ωs + ω 2 t. x = ω 2 s + ωt. 3 x 3 + px + q = 0. T 2 + qt p3 27 = 0. 2 3 2 n 106 3 x 3 + 3x 2 + 4x + 7 = 0.

4.6. 2 123 2017.1.12, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 4.6 2 2 x 2 + ax + b = 0 2 x = α, β { α + β = a αβ = b x 2 + ax + b = x αx β = x 2 α + βx + αβ 4.6.1 3 i. 3 x 3 + px + q = 0 x = u + v ii. u v iii. u 3 =, v 3 = 3 3 1 3 ω u, v iv. u 3 + v 3 u 3 v 3 u 3 v 3 2 v. u 3 v 3 uv 3 vi. x 3 + px + q = 0 x = u + v u 3 + v 3 + q + u + v3uv + p = 0 uv = p 3 u3 + v 3 = q

124 4 3 3 i. x 3 + ax 2 + bx + c = 0 x = t a 3 t 3 + pt + q = 0 a = 0 ii. t 3 + pt + q = 0 t = u + v u 3 + v 3 = q u 3 v 3 = p3 27 u, v iii. u 3 v 3 2 T 2 + qt p3 27 = 0 { m = 3 α α, β n = 3 β iv. ω 1 3 x = m + n a 3 x = mω + nω 2 a 3 x = mω 2 + nω a 3 107 3 ω 3 = 1, ω 1 ω x 3 6x 2 + 6x 2 = 0 108 3 i. x 3 + 3x 6 = 0 ii. x 3 + 3x 2 6 = 0

4.7. 3 125 2016.1.16, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 4.7 3 109 ω 2 + ω + 1 = 0 x 1 + x 2 + x 3 = p x 1 + ωx 2 + ω 2 x 3 = q x 1 + ω 2 x 2 + ωx 3 = r. x 1, x 2, x 3 p, q, r 110 ω 2 + ω + 1 = 0 x 1 + ωx 2 + ω 2 x 3 3 + x 2 + ωx 1 + ω 2 x 3 3 S 3 = 1 2, 2 3 1 2 2 3 4.8 i. 3 x 3 + ax 2 + bx + c = 0 ii. x = t a 3 t3 + pt + q = 0 a = 0 iii. t = t 1 x = t 1 a 3 iv. t = u + v u + v 3 + pu + v + q = 0. u 3 + v 3 + q + u + v3uv + p = 0. { u 3 + v 3 = q, v. 3uv + p = 0 uv = p 3, u 3 + v 3 = q, u 3 v 3 = p3 27,.

126 4 3 vi. u 3, v 3 T 2 + qt p3 27 = 0 α, β u 3 = α, v 3 = β vii. u, v = { 3 α 3 β, { ω 3 α ω 2 3 β, { ω 2 3 α ω 3 β viii. t = 3 α + 3 β, ω 3 α + ω 2 3 β, ω 2 3 α + ω 3 β. ω ω 3 = 1, ω 1 ix. x = 3 α + 3 β a 3, ω 3 α + ω 2 3 β a 3, ω2 3 α + ω 3 β a 3 4.9 3 3 3 0 a 2 x 2 = a 0 a a i. 3 ii. n, 3 2 3 2 4.10 x 3 + px + q = 0.

4.10. 127 x 1, x 2, x 3 x 1 + x 2 + x 3 = 0, x 1 x 2 + x 2 x 3 + x 1 x 3 = p, x 1 x 2 x 3 = q. x 1 + ωx 2 + ω 2 x 3 ω 3 = 1, ω 1. ω 2 + ω + 1 = 0. σ S n f σ x 1, x 2,, x n = fx 1, x 2,, x n fx 1, x 2,, x n S n S n S 3 = 1 2, 1 2 3 { f 1 2 x 1, x 2, x 3 = fx 2, x 1, x 3 = fx 1, x 2, x 3, f 1 2 3 x 1, x 2, x 3 = fx 2, x 3, x 1 = fx 1, x 2, x 3. fx 1, x 2, x 3 1 2x 1 + ωx 2 + ω 2 x 3 = x 2 + ωx 1 + ω 2 x 3 1 2 3x 1 + ωx 2 + ω 2 x 3 = x 2 + ωx 3 + ω 2 x 1 = ω 2 x 1 + ωx 2 + ω 2 x 3 1 2 3 ω 2 ω 3 = 1 1 2 3x 1 + ωx 2 + ω 2 x 3 3 = ω 6 x 1 + ωx 2 + ω 2 x 3 3 = x 1 + ωx 2 + ω 2 x 3 3 x 1 + ωx 2 + ω 2 x 3 3 + x 2 + ωx 1 + ω 2 x 3 3

128 4 3 x 1 + ωx 2 + ω 2 x 3 3 x 2 + ωx 1 + ω 2 x 3 3 1 2 3 1 2 x 1 + ωx 2 + ω 2 x 3 3 x 2 + ωx 1 + ω 2 x 3 3 x 1 + ωx 2 + ω 2 x 3 3, x 2 + ωx 1 + ω 2 x 3 3 2 T 2 + kt + l = 0. k, l l 3 x 1 + ωx 2 + ω 2 x 3, x 2 + ωx 1 + ω 2 x 3. 1 x1 + x 2 + x 3 + x 1 + ωx 2 + ω 2 x 3 + ω 2 x 2 + ωx 1 + ω 2 x 3 3 = x 1 + 1 3 1 + ω + ω2 x 2 + x 3 = x 1. 1 x1 + x 2 + x 3 + ω 2 x 1 + ωx 2 + ω 2 x 3 + ωx 2 + ωx 1 + ω 2 x 3 3 = x 2 + 1 3 1 + ω + ω2 x 1 + x 3 = x 2. 1 x1 + x 2 + x 3 + ωx 1 + ωx 2 + ω 2 x 3 + ωx 2 + ωx 1 + ω 2 x 3 3 = x 3 + 1 3 1 + ω + ω2 x 1 + x 2 = x 3. 3 x 1 + ωx 2 + ω 2 x 3 3

4.11. 129 S 3 2 2 3 5 ζ 5 = 1, ζ 1 5 x 1, x 2, x 3, x 4, x 5 x 1 + ζx 2 + ζ 2 x 3 + ζ 3 x 4 + ζ 4 x 5 5 S 5 24 24 5 6 5 S n S n S 5 A 5 n 4.11 3 x 3 + ax 2 + bx + c = 0 x = x 1, x 2, x 3 a, b, c 3 x 1, x 2, x 3 1 x 1, x 2, x 3 1 1 x 1, x 2, x 3 S 3 2 2 x 1 + ωx 2 + ω 2 x 3 3

130 4 3 4.12 2015 111 2 1 3 4 i. 3 4 2 1 σ 1 2 3 4 σ = 4 3 2 1 ii. 1 2 4 3 τ 1 2 3 4 4 1 2 3 4 3 1 2 τ τ = iii. Z/18Z Z/18Z {0, 1, 2,, 17} Z/18Z 1 2 3 4 5 112 i. σ = 4 5 1 3 2 a σ b σ 5 c σ

4.12. 2015 131 ii. 1 2 3 4 5 6 4 6 5 1 3 2 1 2 3 4 5 6 1 2 3 4 5 6 113 i. 3 1000 a mod 71 a 0 a 70 71 ii. σ 1 = x + y, σ 2 = xy 2x + y 4 + x + 2y 4 σ 1 σ 2 114 3 1 3 ω x 3 3x 2 3x 7 = 0