2

April, 2010

2

Contents 1 7.......................... 7 1.1........................................ 7 1.2..................................... 8 1.3.................................. 8 1.4........................................ 9 1.5...................................... 10.................................... 10 1.6 Eratosthenes.................................... 10 1.7...................................... 11 1.8 Fermat Mersenne................................ 12 2 13....................................... 13 2.1................................. 13 2.2........................................... 14................................... 15 2.3 Wilson....................................... 15 2.4........................................ 15 2.5 Euler.................................... 17.................................... 18 2.6................................. 18 2.7.................................. 19 2.8................................... 20 3 23 p...................................... 23 3.1...................................... 23 3.2..................................... 24 3.3................................. 25 3

4 CONTENTS...................................... 26 3.4 Gauss........................................ 26 3.5................................... 27 3.6................................... 28 3.7............................... 29.................................. 30 3.8................................. 31 3.9 Gauss.................................... 32 3.10 Gauss.................................... 33 3.11........................................... 34 m...................................... 34 3.12 m................................. 35 3.13........................................... 37 3.14...................................... 38.............................. 38 3.15..................................... 38 3.16................................... 40 3.17..................................... 41.............................. 42 3.18.................................. 42 3.19...................................... 44 3.20....................................... 45 3.21.................................... 46 4 47.............................. 47 4.1 pot....................................... 47 4.2 Euler............................... 50 4.3 Dirichlet...................................... 51................................... 51 4.4................................... 51 4.5............................... 52 4.6........................................ 53...................................... 56 4.7........................................ 56 4.8 Fermat................................... 57 4.9........................................ 58 4.10...................................... 61

5

6 CONTENTS

Chapter 1 1.1 a, b b > 0 q, r a = bq + r, 0 r < b Euclid a, b a > b, a = bq 1 + b 1 b = b 1 q 2 + b 2 b n = b n+1 q n+2 + b n+2, b n+2 = 0 b n+1 = (a, b) (a, b) = (a b, b) = (a 2b, b) = = (b 1, b) = (b b 1, b 1 ) = = (b 2, b 1 ) = = (b n+1, b n ) = b n+1 1.1.1. a, b u, v (a, b) = au + bv 1.1.2. a, b, c (a, b) = 1 a bc = a c 7

8 CHAPTER 1. (a, b) = 1 u, v 1 = au + bv a a c c = acu + bcv p p ab = p a p b 1.2 a, b, m a m b a b (mod m) a b m m a b 17 10 3 (mod 7) : Eulcid a > b > 0 a b 1 (mod b) b 1 0 b 1 < b b b 2 (mod b 1 ) b 2 0 b 2 < b 1 b n 1 b n+1 = 0 (mod b n ) (a, b) = b n 1.1.1 a, b v bv (a, b) (mod a) (a, b) = 1 bv 1 (mod a) (a, b) = 1 v bv 1 (mod a) bc 0 (mod a) v c bvc 0 (mod a) 1.3 1.3.1. 1 n > 1 n a, b n = ab a b n = p 1 p s = q 1 q t,

1.4. 9 p 1 q 1 q t p 1 q i p 1 q 1 p 1, q 1 p 1 = q 1 p 2 p s = q 2 q t, 1.4 1 α = a b = c d, (a, b) = (c, d) = 1 ad = bc a bc (a, b) = 1 a c c a, a = c, b = d α 2 (a, b) = 1 (a + b, a b) = 1 2 (a+b, a b) = d d a+b+(a b) = 2a, d a+b (a b) = 2b d (2a, 2b) = 2 3 n 1000 n 1 1978 n 1 1000 n 1 1978 n 1 1000 n 1 1978 n 1 (1000 n 1) = 1978 n 1000 n = 2 n (989 n 500 n ) (1000 n 1, 2 n ) = 1 1000 n 1 989 n 500 n 0 < 989 n 500 n < 1000 n 1 4 p 1 < r < p p ( ) p r ( p r) r! p(p 1) (p r + 1) r! p p r! p (r!, p) = 1 r! (p 1) (p r +1) p ( ) p r 5 a, b, c (a, b) = 1 ab = c n a = c n 1, b = cn 2 a = p α 1 1 pαr r b = q β 1 1 qβs s c = p l 1 1 p lr r q m 1 1 qs ms ab = c n n α i β j a, b n 6 x 2 + y 2 = z 2 x > 0, y > 0, z > 0 x, y, z x, y, z 4 z x y x 2 = z 2 y 2 ( x 2 )2 = ( z + y 2 )(z y 2 )

10 CHAPTER 1. (z, y) = 1 2 ( z+y 2, z y 2 ) = 1, 5 z + y 2 = a 2, z y 2 = b 2, x = 2ab x = 2ab, y = a 2 b 2, z = a 2 + b 2 (a, b) = 1 1.5 1 2 Gauss Z[i] = {a + bi a, b Z} Z[i] (1) Z[i] Z[i] (2) Z[i] (3) Z[i] Z[i] (4) 3 6 x 2 + y 2 = 1 (-1,0) 4. x 4 + y 4 = z 2 1.6 Eratosthenes N N N 2 2 3 3 N 1: 100 2 3 5 7 2: 137 2 3 5 7 11 3 1000 a a+2, a 2 a = n 2 a+2, a 2 n n 3 a + 2 3 n 27, 21... 17 27 2 + 2 21 2 + 2, 21 2 2 21 2 = 441 1.6.1. p 1, p 2,..., p k k p 1 p 2 p k + 1 k 1.6.2. 4n 1 p 1, p 2,..., p k k 4n 1 4p 1 p 2 p k 1 4n 1

1.7. 11 1.6.3. (a, b) = 1, a + bn 1.6.4. Fields : Goldbach 1.7 a 1 x 1 + + a r x r = n (1) a 1,..., a r 0 1.7.1. (1) (a 1,..., a r ) n A = a 1 Z + + a r Z d A = dz A d A A dz a A a dz a = dq + b, 0 < b < d A b = a dq A d A = dz d (a 1,..., a r ) r = 2 1.1.1 ax + by = n (2) (a, b) = 1 1.7.2. (x 0, y 0 ) (1) x = x 0 + bt, y = y 0 at, t Z ax + by = ax 0 + by 0 a(x x 0 ) = b(y 0 y), b a(x x 0 ) (a, b) = 1 b x x 0 x x 0 = bt x = x 0 + bt y = y 0 bt a, b, n n a, b (2) n 1.7.3. n = ab a b (2) n > ab a b (2) a = 8, b = 15 ab a b = 97 n 97 100

12 CHAPTER 1. 8x + 15y = 97 x 97 8x 15 8x 97 7 (mod 15) 8x 8 (mod 15) (8, 15) = 1 x 1 14 (mod 15). x 14 x y x y 97 8 14 15 = 1 x, y 8x + 15y = 100 15 8x 100 (mod 15), 2x 25 10 (mod 15), x 5 (mod 15) x = 5 y = 4 x, y ax + by = ab a b (3) x ax ab a b a (mod b), x 1 (mod b) x b 1 y = 1 (3) x, y (2) n > ab a b r y x 0 r b 1 y = n ar b > ab a b a(b 1) b = 1 y y 0 1.8 Fermat Mersenne M p = 2 p 1 Mersenne F n = 2 2n + 1 Fermat 1.8.1. Fermat F n (F n 2)(F n+1 2) (F n+m 1 2) = F n+m 2 Fermat F n F 0,..., F 4 F 5 1.8.2. M p 2pk + 1 1.8.3. a, b, s (s a 1, s b 1) = (s (a,b) 1) d s a s b 1 (mod d). r s r 1 (mod d) r a, r b r (a, b) s (a,b) 1 (mod d) d s (a,b) 1) Fermat

Chapter 2 2.1 a, b, m a m b a b (mod m) a b m m a b a b (mod m), c d (mod m) = a + c b + d (mod m), ac bd (mod m) f(x) a b (mod m) = f(a) f(b) (mod m) 1 2 100 7 2 100 (2 3 ) 33 2 1 33 2 2 (mod 7) {a + mz} = {x Z x a b a + mz, a + mz = b + Z 2 8 1 8 8 8 8 4 1 3 5 7 m m a 1, a 2,..., a m m m 0, 1,..., m 1 1, 2,..., m (a, m) = 1 = b a + mz, (b, m) = 1, 13

14 CHAPTER 2. m m φ(m); a 1, a 2,..., a φ(m) φ(m) m φ(m) Euler φ(1) = 1 (a, m) = 1 ax b (mod m) m m 2.2 2.2.1. (a, m) = 1 r a r 1 (mod m); r a d 1 (mod m) d r d a, a 2, a 3,... m i > j > 0 a j a i = a j a i j (mod m) a i j 1 r d d = qr + s, 0 < s < r a s a d 1 (mod m) r 2.2.2. a r 1 (mod m) r a m 3 2 7 3 2 d 1 (mod 7) 3 d 4 n m n m r 10r 1 (mod m) (10, m) = 1 10 7 6 1 7 6 10 49 42 1 49 42 2.2.3. Fermat p a a p a (mod p) (a, p) = 1 a p 1 1 (mod p) a, b (a+b) p = a p +b p + (mod p) p 1 i=1 ( p ) i a p +b p a a 1 a p a 2.2.4. Euler a, m (a, m) = 1 a φ(m) 1 (mod m) a 1, a 2,..., a φ(m) m aa 1, aa 2,..., aa φ(m) a 1 a 2 a φ(m) aa 1 aa 2 aa φ(m) a φ(m) a 1 a 2 a φ(m) a φ(m) 1 (mod m) Euler Fermat 10 49 42 10 7 6 Fermat 10 2, 10 3 mod 7 10 49 r Euler d φ(49) = 42 10 d 1 (mod 7) 6 d d = 6 42 10 d 1 (mod 49) d = 42

2.3. WILSON 15 1 7 = 0.142857, 2 7 = 0.285714, 3 7 = 0.428571,... i 7 p 1 p p 1 p m 2.3 Wilson 2.3.1. Wilson p (p 1)! 1 (mod p) p = 2 p i A = {1, 2,..., p 1} i A ii 1 (mod p) i i i = i i 2 1 i (p 1)! = i i 1 ( 1) 1 (mod p) i A i 2 p 1 (mod 4) a p a 2 + 1 (p i) i (mod p), i = 1,..., p 1 2 p 1 p 1 (p 1)! ( 2 )!( 1) (mod p) Wilson (( p 1 2 )!)2 1 (mod p) p (( p 1 2 )!)2 + 1 2 ( p 1 2 )! (( p 1 2 )!)2 Wilson 2.4 x a 1 (mod m 1 ) x a n (mod m n ) m 1, m 2,..., m n a 1,..., a n m = m 1 m n a a + mz x a i a (mod m i ) m i x a m i m x a x a (mod m) Chinese remainder theorem 2.4.1. m 1, m 2,..., m n m = m 1 m n M i = m m i x a, a = a 1 M 1 + + a n M n, M i M i 1 (mod m i )

16 CHAPTER 2. n x 0 (mod m 1 ) x a i (mod m i ) x 0 (mod m n ) i = 1,..., n n x 0 (mod m 1 ) x 1 (mod m i ) x 0 (mod m n ) a i x 1 (mod m i ) x 0 (mod M i ) M i y 1 (mod m i ) (m i, M i ) = 1 M i n M i x 2 (mod 4) x 3 (mod 25) 4x 1 (mod 25) x 19 (mod 25) 25x 1 (mod 4) x 1 (mod 4) 76 0 (mod 4) 76 1 (mod 25) 25 1 (mod 4) 25 0 (mod 25) x 2 25 + 3 76 78 (mod 100) : 76 2009 + 25 2009 76 0 (mod 4) 76 1 (mod 25)

2.5. EULER 17 76 2 76 (mod 100) 25 2 25 (mod 100) 76 2009 + 25 2009 76 + 25 1 (mod 100), 0 1 76 25 x 2 x 0 (mod 100) 2.5 Euler φ(p r ) = p r p r 1 φ(n) 2.5.1. m 1, m 2 φ(m 1 m 2 ) = φ(m 1 )φ(m 2 ) : A, A 1, A 2 m = m 1 m 2 m 1 m 2 A A 1 A 2 σ : a (a 1, a 2 ), a i a a i (mod m i ) a b (mod m i ), i = 1, 2 = a b (mod m) A B C σ B A B 1 A 1 B 2 A 2 m m 1 m 2 (a, m) = 1 (a, m 1 ) = (a, m 2 ) = 1 (a 1, m 1 ) = (a 2, m 2 ) = 1 σ B B B 1 B 2 φ(m 1 m 2 ) = φ(m 1 )φ(m 2 ) n = p l 1 1 p lr r φ(n) = (p l 1 1 p l 1 1 1 ) (p lr r p lr r ) = n p n(1 1 p ) C i 1, 2,..., n p i φ(n) = n C 1 C r = n C i C j = n p i p j φ(n) = n 1 i r 1 i r C i + 1 i<j r C i C j + ( 1) r C 1 C r n + + ( 1) r n = n (1 1 ) p i p 1 p r p i 1 i r φ(n) = n p n(1 1 p ) : C 1,..., C r C 1 C r = C i C i C j + + ( 1) r 1 C 1 C r 1 i r 1 i<j r

18 CHAPTER 2. Euler φ(d) = n d n n (x, n) A = [1, n] Z A d = {x A (x, n) = d}. A d = φ( n d ) A = d na d (x, n) = d x = dy, n = d n d, (y, n d ) = 1 n = d n φ( n d ) = d n φ(d) 1. 2 2100 2. n n 9 n 3 (mod 504) 3. n 2 n n 2 7 4. 10000 n 2 n + n 2 100 5. n = pq p, q n? (mod n) 2.6 f(x) m f(x) 0 (mod m) (1) m 4x 10 (mod 14) (2) 2x 5 (mod 7) (3) (3) x 6 (mod 7) (2) x 6 (mod 14) x 13 (mod 14) (1) 0, 1, 2,..., m 1 m m m = p l 1 1 p lr r (1) r f(x) 0 (mod p l i i ), i = 1,..., r x a i (mod p l i i ) (1) m

2.7. 19 2.6.1. f(x) 0 (mod p l i i ) n i i = 1,..., r m = p l 1 1 p lr r (1) n 1 n r : 1 x 2 x 0 (mod 100) x 2 x 0 (mod 4) x 2 x 0 (mod 25) x 0, 1 (mod 4) x 0, 1 (mod 25) x 0, 1, 76, 25 (mod 100) (1) 2.7 f(x) 0 (mod p l ) = f(x) 0 (mod p l 1 ) f(x) 0 (mod p l ) f(x) 0 (mod p), f(x) 0 (mod p 2 ),... Hensel f(x) 0 (mod p) f(x) 0 (mod p l ) 2.7.1. Hensel a 0 f(a 0 ) 0 (mod p) f (a 0 ) 0 (mod p) a 1, a 2,..., 0 a i p 1 l > 1, (2) f(x) 0 (mod p l ) x a 0 (mod p) x a 0 + a 1 p + + a l 1 p l 1 (mod p l ) f(x) 0 (mod p l ), l = 2, 3,... x = a 0 + px 1 f(x) 0 (mod p 2 ) f(a 0 + px 1 ) f(a 0 ) + f (a 0 )px 1 0 (mod p 2 ), f (a 0 )x 1 f(a 0) p (mod p) x 1 a 1 (mod p 2 ) (2) l = 2 x a 0 + a 1 p x α l 2 = a 0 + a 1 p + + a l 2 p l 2 (mod p l 1 ) f(x) 0 (mod p l 1 ) x a 0 (mod p) x = α l 2 + p l x xl (2) f (α l 2 )x l 1 f(α l 2) p (mod p) f (α l 2 ) f (a 0 ) 0 (mod p) x l 1 a l 1 (mod p) (2) x α l 2 + p l 1 a l 1 = a 0 + a 1 p + + a l 1 p l 1 (mod p l ) (mod p l )

20 CHAPTER 2. 2 7x 4 + 19x + 25 0 (mod 27) 7x 4 + 19x + 25 0 (mod 3) x 1 (mod 3) x = 1 + 3y 7x 4 + 19x + 25 0 (mod 9) (3) 6 + 6y 0 (mod 9) y 2 (mod 3) (3) x 7 (mod 9) x = 7 + 9z 18 + 9z 0 (mod 27) x 1 (mod 3) x 16 (mod 27) 3 x p 1 1 0 (mod p l ) Fermat f(x) = x p 1 1 0 (mod p) p 1 1, 2,..., p 1 f (x) x p 1 Hensel p 1 1. f (a) 0 (mod p) f(x) 0 (mod p 2 ) x a (mod p) 0 p 2. a 1,..., a n p (x a 1 ) (x a n ) 0 (mod p 3 ) 3. x(x 1)(x 2)(x 5) 0 (mod 5 3 ) 4. x p 1 1 0 (mod p l ) x a pl 1 (mod p l ), a = 1, 2,..., p 1 2.8 2.8.1. f(x) 0 (mod p) f(x) degf

2.8. 21 ab 0 (mod d) = a 0 (mod p) 0 (mod p) f(x), g(x) {x Z f(x)g(x) 0 (mod p)} = {x Z f(x) 0 (mod p)} {x Z g(x) 0 (mod p)}, f(x) = (x a)g(x) + f(a) f(a) 0 (mod p) a, f(x) (x a)g(x) (mod p) Wilson Fermat x p 1 1 0 (mod p) p 1 1, 2,..., p 1 x p 1 1 (x 1)(x 2) (x (p 1)) (mod p) 1 ( 1) p 1 (p 1)! (p 1)! (mod p) 2.8.2. d p 1 (1) x d 1 0 (mod p) d (2) a b a b d a p d a d a p 1 d 1 (mod p) (1) x p 1 1 0 (mod p) p 1 x d 1 x p 1 1 x d 1 0 (mod p) d (2) =. a b d a p 1 d b p 1 1 (mod p) (1) p 1 d d 1d, 2 d,..., (p 1) d p 1 p 1 b x d b d (mod p) x d x bα i, i = 1,..., d alpha i x d 1 0 (mod p) d 1 d, 2 d,..., (p 1) d d d p 1 d a (a, m) m 1. n d = (n, p 1) (1) x n 1 (mod p) x d 1 (mod p), (2) a n a d 2. a p d a i p d (i,d) d ai i d 3. d n φ(d) = n p p 1

22 CHAPTER 2.

Chapter 3 p 3.1 p g p p 1 g p g, g 2,..., g p 1 1 (mod p) p 3 7 3 3,2,6,4,5,1 3 p A p A d A d A = d p 1 A d A = A d (1) d p 1 A d = φ(d) A d > 0 = A d = φ(d), A d = 0 φ(d) A d φ(d) (1) p 1 = A d φ(d) = p 1 d p 1 d p 1 d p 1 φ(d) φ(p 1) 3.1.1. a m b n (m, n) = 1 ab mn d p 1 p 0 x d 1 (mod p) (2), 23

24 CHAPTER 3. (2) d p 1 d = p 1 a d b n < d n d n = p s n, d = p t d, s > t a n p s b pt d a n b pt p s d > d d p 1 p 1 = p l 1 1 p lr r p l i i 3.2 3.2.1. a p p 1 q a p 1 q 1 (mod p) a d a p 1 d > 1 q p 1 d q d p 1 q a q n q a p 1 q 1 (mod p) a d a n 1 (mod p) n q 1 (mod p) d n p q r n q r n q 2 2 13 2 12 3 3, 2 12 2 1 (mod 13) 3 p 1 > p 2 m p 1 p 2 m p 1 p 2 + 1 m m p 1 p 2 1 (mod p 1 ) m p 1 p 2 1 (mod p 2 ) Fermat m p2 1 1 (mod p 1 ) m p1 1 1 (mod p 2 ) m 2(p2 1) 1 (mod p 1 ) m (p 2 1) 1 (mod p 1 ) m p 1 d 2(p 2 1) 2 d p 1 1 p 1 1 2 > p 2 1 2 p 2 1 2 > p 1 1 2

3.3. 25 p dd = p 1 = p l 1 1 p lr r g p a 0 (mod p) (1) a d (2) g i a (mod p) i d (3) a d 1 (mod p) (1) a d d s p 1, s > d s a s (2) g i a (mod p) i (i, p 1) = d (3) α α d a (mod p) (4) a d d = 1 (1) p 1 > 1 s a s (2) p 1 q a q (3) p 1 q a p 1 q 1 (mod p) (4) g i a (mod p) i (i, p 1) = 1 (5) a a p 1 2 mod p a 3.3 3.3.1. p p a p x 2 a (mod p) d d = 2 a p 1 2 ±1 (mod p) 3.3.2. ( p ) a a p 1 2 1 (mod p) a a p 1 2 1 (mod p) ( a p ) = 1, a 1, ( a p ) a p 1 2 (mod p)

26 CHAPTER 3. ( ab p ) (a p )( b ) (mod p) p ( 1 p 1 ) ( 1) 2 (mod p) p ±1 p > 2 : (1) ( a p ) a p 1 2 (mod p) (2) ( ab p ) = ( a p )( b p ) (3) ( 1 p 1 p ) = ( 1) 2 (4) ( 2 p ) = ( 1) p2 1 8 (2),(3),(4) : (5) p q ( q p )(p q p 1 q 1 )( ) = ( 1)( 2 2 ) ( q p ) = ( p q ( p q ), p 1 (mod 4) q 1 (mod 4) ), p q 3 (mod 4) ( 5 353 ) = ( 353 5 ) = ( 3 5 ) = 1 5 353 ( 17 41 ) = (41 17 ) = ( 7 17 ) = (17 7 ) = (3 7 ) = (7 3 ) = (1 3 ) = 1 p = 13 ( 2 13 ) ( 2 p ) A = {1, 2, 3, 4, 5, 6} A ( A) 2A = 2, 4, 6, 8, 10, 12 {2, 4, 6, 5, 3, 1} 2 6 1 (mod 13) ( 2 13 ) = 1 2 6 (6!) = i ( 1) 3 (6!) (mod 13) i 2A 3.4 Gauss Gauss Gauss ( 2 p ) ( 2 13 ) A = {1, 2,..., p 1 2 } p {1, 2,..., p 1} = A (p A);

3.5. 27 A ( A). 2A = {x 1,..., x n } {y 1,..., y m } {x 1,..., x n } = 2A A, {y 1,..., y m } = 2A (p A) 2A ( 2A) p x 1,..., x n, y 1,..., y m p A = {x 1,..., x n, p y 1,..., p y m } 2 p 1 2 i ( 1) m x 1 x n y 1 y m i A i = i = x 1 x n y 1 y m i A i 2A 2 p 1 2 ( 1) m ( 2 p ) = ( 1)m m :m 2A p 2 A p 4 m = [ p 2 ] [ p 4 ] p 2 1 8 (mod 2) ( 2 p ) = ( 1) p2 1 8 (mod p) : A = {a 1,..., a p 1 } p A ( A) 2 a 0 (mod p) aa aa i = ε i b i, ε i = ±1, b 1,..., b p 1 a 1,..., a p 1 2 2 p 1 i aa i a 2 ε 1 ε p 1 ( 1) m m ε 1,..., ε p 1 1 2 2 p aa A Gauss 3.4.1. A p a 0 (mod p) aa = {x 1,..., x n, y 1,..., y m } {x 1,..., x n } A {y 1,..., y m } A ( a p ) = ( 1)m A = {1, 2,..., p 1 2 } Gauss 3.4.2. a, 2a,..., p 1 2 a p > p 2 m ( a p ) = ( 1)m 3.5 p, q q, 2q,..., p 1 2 q kq = pq k + r k, 0 < r k < p

28 CHAPTER 3. {r 1,..., r p 1 } = {x 1,..., x n, y 1,..., y m } x i 2 < p 2 y j > p p 1 2 A = {1, 2,..., 2 } = {x 1,..., x n, p y 1,..., p y m } p 1 2 r k = k=1 n m x i + y j (1) i=1 j=1 (1) kq pq k r k q p 1 2 k = n m x i + (p y j ) (2) k=1 i=1 j=1 p 1 2 k p p 1 2 q k = k=1 k=1 i=1 j=1 n m x i + y j (3) (2),(3) m m m mod 2 2 p q 1 (mod 2) m p 1 2 q k p 1 k=1 k=1 2 [ kq ] (mod 2) p ( q p ) = ( 1) ( p q ) = ( 1) ( q p )(p q ) = ( 1) p 1 2 k=1 q 1 2 k=1 [ kq p ] [ kp q ] p 1 q 1 2 [ kq p ]+ 2 [ kp q ] k=1 k=1 p 1 2 [ kq p ] + k=1 q 1 2 [ kp q ] = p 1 2 k=1 q 1 2 {(x, y) 0 < x < p 2, 0 < y < q p 1 q 1 2 } 2 2 y = q p x p 1 q 1 2 [ kq p ] 2 [ kp q ] (4) k=1 k=1 (4) 3.6 3.6.1. n = p l 1 1 p lr r n m Jacobi ( m n ) = ( m p 1 ) l1 ( m p r ) lr

3.7. 29 : ( m n ) = 1 x2 m (mod n) ( m n ) = 1 x2 m (mod n) Jacobi (1) a b (mod n) ( a n ) = ( b n ) (2) ( ab n ) = ( a n )( b n ) (3) ( 1 n 1 n ) = ( 1) 2 (4) ( 2 n ) = ( 1) n2 1 8 (5) m n ( m n )( n m 1 )( ) = ( 1)( n 1 2 2 ) m (3) n = p l 1 1 p lr r (3) a, b p l 1 1 p lr r 1 p 1 1 p r 1 l 1 + + l r 2 2 2 a 1 2 + b 1 2 ab 1 2 (mod 2) (mod 2) Jacobi ( a p ) a ( 143 353 ) = ( 353 143 ) = ( 67 143 143 ) = ( 67 ) = ( 9 67 ) = 1 ( 129 353 ) = ( 353 129 ) = ( 95 129 ) = ( 129 95 ) = ( 34 95 ) = ( 2 17 95 )( 95 ) = ( 17 95 ) = ( 95 17 ) = ( 10 17 ) = ( 5 17 ) = ( 17 5 ) = ( 2 5 ) = 1 1. Jacobi 2 n 1 3 n 1 2. D D D D, D 1 (mod 4) = 4D, p, q p q (mod D ) = ( D p ) = (D q ) 3.7 x 2 n (mod p) (5) 3.7.1. p ( n p ) = 1 1) p 3 (mod 4) (5) x ±n p+1 4 (mod p)

30 CHAPTER 3. 2) p 5 (mod 8) (5) x ±n p+3 8 (mod p), n p 1 4 1 (mod p) ±n p+3 8 ( p 1 2 )! (mod p), n p 1 4 1 (mod p) 1) n p 1 2 1 (mod p) p 1 2 1 n n p 1 2 +1 = (n p+1 4 ) 2 (mod p) (5) 2) n p 1 2 1 (mod p) p 1 2 2 n p 1 4 ±1 (mod p) n p 1 4 1 (mod p) p 1 4 1) x ±n p+3 8 (mod p) n p 1 4 1 (mod p) n (n p+3 8 ) 2 (p 1)!(n p+3 8 ) 2 ( p 1 2!)2 (n p+3 8 ) 2 (mod p) (5) 1) p 1 2 2) p 1 2 p 1 2 p 1 (mod 8) c 3.7.2. p ( n p ) = 1 l x 2 n (mod p l ) (6) f(x) = x 2 n (5) ±x 0 f (±x 0 ) = ±2x 0 0 (mod p) Hensel p = 2 (6) (6)

3.8. 31 3.8 3.8.1. p p p = 2 p 1 (mod 4) p 1 (mod 4) = m, p m 2 + 1 3.8.2. m 2 + 1 3.8.3. (x, y) = 1 x 2 + y 2 x 2 + y 2 p x2 +y 2 p p = a 2 + b 2 a 2 b 2 (mod p) x 2 y 2 (mod p) a 2 x 2 b 2 y 2 (mod p) ax ±by (mod p) ax by (mod p) x 2 + y 2 p = (a2 + b 2 )(x 2 + y 2 ) p 2 = (ax by)2 + (ay + bx) 2 p 2 = ( ax by ) 2 ay + bx + ( ) 2 p p p ax by p (a 2 + b 2 )(x 2 + y 2 ) = (ax by) 2 + (ay + bx) 2 p ay + bx x2 +y 2 p d ( ax by p ( ax by ) 2 ay + bx + ( ) 2 p p, ay+bx p ) ax by ay + bx d a + b = x p p d y (x, y) = 1 d = 1 3.8.2 m m = 1 < m p m 2 + 1 p < m p (m p) 2 + 1 p p > m m2 +1 p = p 1 p r < m p i < m p i p = m2 +1 p 1 p r 3.8.1

32 CHAPTER 3. 3.9 Gauss a 2 + b 2 = (a + bi)(a bi) Gauss Z[i] = {a + bi a, b Z} Z[i] Gauss Z Gauss 3.9.1. Z[i] ±1, ±i : a+bi Z[i] 1 a+bi = a bi Z[i] a b, Z a+bi = ±1, ±i a 2 +b 2 a 2 +b 2 a 2 +b 2 3.9.2. α Z[i] α β β α β 3.9.3. α = a + bi N(α) a 2 + b 2 α, β Z[i] β 0 γ, λ Z[i] ; γ Z[i] α = λβ + γ N(γ) < N(β) α γ (mod β) N(γ) < N(β) N(α) N(β) α β : u = ±1, ±i α uβ < α u 1 = ±1 α u 1 β u 2 = ±i α u 2 u 1 β 45 α u 2 u 1 β < α α β = λ + δ λ Z[i], δ = a + bi, a, b Q, a 1 2, b 1 2 N(δ) = a 2 + b 2 1 2 < 1 α = λβ + δβ δβ = α λβ Z[i] N(δβ) = N(δ)N(β) < N(β) γ = δβ 3.9.4. α, β Z[i] αz[i] + βz[i] γz[i] γ α β αz[i] + βz[i] N(γ) 3.9.5. Z[i] Z[i] 3.9.6. a + bi Z[i] a b

3.10. GAUSS 33 Gauss Gauss Gauss 3.9.7. p p p = a 2 + b 2 p = (a + bi)(a bi) p p = (a + bi)(c + di) p 2 = (a 2 + b 2 )(c 2 + d 2 ), a 2 + b 2 > 1, c 2 + d 2 > 1 a 2 + b 2 = p = c 2 + d 2 3.9.8. Gauss a + bi a 2 + b 2 : a+bi a+bi = (c+di)(a+bi) a+bi, c+di a 2 +b 2 = (c 2 +d 2 )(A 2 +B 2 ) a 2 +b 2 a 2 +b 2 = mn m, n 1 (a + bi)(a bi) = mn a bi m, n m, n a + bi, a bi 3.10 Gauss Gauss 3.8.2 p m 2 + 1 = (m + i)(m i) p m + i, p m + i Gauss p 3.9.7 p 3.8.3 3.8.3 a 2 + b 2 = p 3.9.8 a + bi (a + bi)(a bi) = p x 2 + y 2 a + bi (x + yi)(x yi) a + bi x + yi a + bi x yi (a + bi)(c + di) = x + yi (a 2 + b 2 )(c 2 + d 2 ) = x 2 + y 2 c 2 + d 2 = x2 +y 2 p c, d c + di = x + yi a + bi = (a bi)(x + yi) a 2 + b 2 = ax + by p + ay bx i p c = ax+by p, d = ay bx p Gauss 1 y 2 + 1 = x 3 y (y + i)(y i) = x 3

34 CHAPTER 3. y + i y i π π 2i = (1 + i) 2 π = 1 + i y = 2n = i(1 + i) 2 n y + i i (mod 1 + i) 1 + i y + i y + i y i y + i = u(a + bi) 3, u ±1, ±i y + i = (a + bi) 3 1 = 3a 2 b b 3 = b(3a 2 b 2 ) b = ±1 b = 1, a = 0 x = 1, y = 0 2 x 2 + y 2 = z 1 0, (x, y) = 1 x, y x + yi, x yi x + yi = u(a + bi) 1 0 u = ±1, ±i 3.11 Gauss Z Z Gauss (1)pu p 4k + 3 u (2) N(α) α Gauss Z[ d] d Z[ d] 1. Gauss x + yi 0 (mod 1 + i), x y (mod 2) x + yi 1 (mod 1 + i), x y (mod 2) 2. 2 Gauss 3. Z[ 2] p 4. y 2 + 2 = x 3 5. y 2 + 5 = x 3 p a 2 + 2b 2 ( 2 ) = 1 p 1, 3 (mod 8) p m

3.12. M 35 3.12 m m > 1 g m g m φ(m) g m m 3.12.1. m = m 1, m 2 (m 1, m 2 ) = 1 a m i r i i = 1, 2 a m r 1 r 2 [r 1, r 2 ] n a n 1 (mod m) i = 1, 2, a n 1 (mod m i ) i = 1, 2, r i n [r 1, r 2 ] n 3.12.2. m m p l, 2p l p 2 a m = p l 1 1 p lr r φ(m) = φ(p l 1 1 ) φ(p lr r ) m [φ(p l 1 1 ),..., φ(p lr r )] m φ(p l i i ) m m m = 2 a p l φ(2 a ) p 1 a = 0, 1 m p n 3.12.3. p n 3.12.4. p n a b (mod p n ) = a p b p (mod p n+1 ) a p n+1 = a p n a p n r < φ(p n ) a r 1 (mod p n ) 3.12.3 a rp 1 (mod p n+1 ), rp < pφ(p n ) = φ(p n+1 ) a p n+1 p p n 3.12.5. p g p (1)g p 1 1 (mod p 2 ) = n, g p n (2)g p 1 1 (mod p 2 ) = n, g p n

36 CHAPTER 3. (1) g p n r g r 1 (mod p) p 1 r r φ(p n ) = p n 1 (p 1) r = p h (p 1), h n 1 g p n h = n 1 g pn 2 (p 1) 1 (mod p n ) (1) g p 1 1 (mod p 2 ) g p 1 1 + ap (mod p 2 ), a 0 (mod p) g p(p 1) (1 + ap) p 1 + ap 2 (mod p 3 ) g pn 2 (p 1) 1 + ap n 1 1 (mod p n ), (1) g p n (2) g p 1 1 (mod p 2 ) 3.12.3 g pn 2 (p 1) 1 (mod p n ) g p n 3.12.6. p n p n g p (g + ap) p 1 g p 1 + a(p 1)p g p 1 ap (mod p 2 ) a p p 1 g + ap (g + ap) p 1 1 (mod p 2 ) g p n g g + p 3.12.7. n 3 2 n a a 2 1 (mod 8) 8 3.12.4 2 n 3.12.8. m m p l, 2p l p 2 4 3.12.2 3.12.7 p n g (g, 2) = 1 n 100 2 n + n 2

3.13. 37 2 n 4 2 n + n 2 25 2 n + n 2 2 n n 2 (mod 25) 2 5 2 4 1 (mod 25) 2 25 2 10 1 (mod 25) 2 n+10 n 2 (mod 25) n 20 2 n+10 20 2 n+10 25 n n 0, 2, 4,..., 18 (mod 20) n ±2 5, ±2 6, ±2 7,..., ±2 14 (mod 25) 20 : n 2k (mod 20), k = 0, 1,..., 9, n ±2 k+5 (mod 25) 4 100 n 6 (mod 20) n ±2 8 (mod 25) n 6 (mod 100) 1. a, b p a b p r a b = p r+1 a p b p p r a b p r a b p r+1 a b : 3.12.3 2. 3.12.5 p = 2 3. p a p n r n r n+1 = r n pr n 3.13 g m (a, m) = 1 d 0 d < φ(m) g d 1 (mod m) d a g ind g a inda indab inda + indb (mod φ(m)) inda n ninda (mod φ(m)) d φ(m) a m d d inda p a p 2 2 inda 49 ind2

38 CHAPTER 3. 3.14 1. RSA m = pq p, q d (d, φ(m)) = 1 m a f(a) = b a d (mod pq), a b e (mod pq) e de 1 (mod (p 1)(q 1)) m d p q φ(m) m e RSA 2. p g inda x n mod p p g a g r (mod p) r r r a x p 2 n g n b (mod p) a n x y (mod p) (b, y) b r x y (mod p) x r 3.15 3.15.1. G G G G G (a, b) a b 1) a, b, c G (a b) c = a (b c) 2) e G a G a e = e a = a

3.15. 39 3) a G b G a b = b a = e b a G (G, ) G a, b G a b = b a G abel : a b = e b a = e a b b = a 1 + abel a na n a G a b ab a n G a, b ax = b ya = b G 1 Z 2 Q R C 3 Q R C 0 abel 4 k n (GL) n (k) k = Q, R C : 5 n > 1 Z/nZ {i + nz i Z} = {i + nz i = 0, 1,..., n 1} :(i + nz) + (j + nz) = {x + y x i + nz, y j + nz} = (i + j) + nz i = i + nz Z/nZ = {i i = 0, 1,..., n 1} abel 0 = nz 6 n > 1 Z/nZ {i i Z, (i, n) = 1} (i)(j) := ij abel (Z/nZ) 1 i = i, j = j = ij = i j (i)(j) = {x i, y j} 3.15.2. G 1 G 2 G 1 G 2 f a, b G 1, f(ab) = f(a)f(b). f G 1 G 2

40 CHAPTER 3. (Z/pZ), Z/(p 1)Z, U p 1 U n = {z C z n = 1} 3.15.3. Z/4Z, (Z/8Z) 3.16 3.16.1. G e a G a r = e r a r 3.16.2. a G r a n = e r n 3.16.3. G n abel n (1) Euler a G a n = e (2) Wilson G 2 (1) abel 3.16.4. G abel a G n a s n (s,n) 3.16.5. G abel a G n b G m n m ab nm 3.16.6. G abel a G a 3.16.7. G G = {a m m Z} G a G 3.16.8. G G Z Z/nZ G = {a m m Z} a G Z a n G Z/nZ 3.16.9. n abel G m n x m = e x m p G G Z/nZ x m = e x m a G m 3.16.6 m G n x m = e n m m m n m = n G a

3.17. 41 3.17 3.17.1. G H (1)a, b H = ab H (2)a H = a 1 H H G G H G H < G G H a G ah = {ah h H} 3.17.2. G H ah bh ah bh G = a G ag 3.17.3. G H G H G 3.17.4. G H H G a G ah = Ha 3.17.5. G H G/H = {ah a G} (ah)(bh) = abh G/H G H : ah = Ha ah = ha h H G abel Z nz Z/nZ {1, 2, 3} S 3 2 3 3 2 3.17.6. G 1 G 2 f a, b G f(ab) = f(a)f(b) e 1 e 2 f(e 1 ) = e 2, f(a 1 ) = f(a) 1 3.17.7. f G 1 G 2 1) Kerf := {x G 1 f(x) = e 2 } G 1 2) G 1 /Kerf G 2 f f f(a) = f(a) :1) Kerf a G 1 x Kerf f(axa 1 ) = f(a)f(x)f(a 1 ) = f(a)f(a 1 ) = f(aa 1 ) = f(e 1 ) = e 2 axa 1 Kerf akerfa 1 Kerf a akerfa 1 Kerf akerfa 1 = Kerf

42 CHAPTER 3. Kerf 2) f a = b a = bx, x Kerf f(a) = f(b)f(x) = f(b)e 2 = f(b) f f f G 2 f(a) = f(a) f f(a) = f(b) f(a) = f(b) f(a)f(b) 1 = e 2 f(ab 1 ) = e 2 ab 1 Kerf akerf = bkerf f f G 1 Z/nZ n XA = α X R n α R m A n m = abel G 1,..., G m G 1 G 2 G m 3.17.8. Z/p r Z G 1 G 2 G m m > 1 G i 1 3.17.9. 1 abel G 1 G 2 G m m > 0 G i 1 1. 72 abel 2. f G 1 G 2 f(g 1 ) G 2 G 1 /Kerf 3.18 3.18.1. R + (R, +, ) R (R, +) 0 1

3.18. 43 1 3.18.2. R R 0 R R ; a, b R ab 0 R 1 Z Z ℸ[X] 2 Q, R, C 3 Z/nZ 4 Z[i] Z[ 2] : 5 M n (k) k n > 1 2 3 2 3 n p Z/nZ R R R k R A L R I a R, b I = ab I, ba I, I R R I R R/I = {a + I a R} (a + I)(b + I) = ab + I R I R/I. a = a + I. 1. 1 φ : Z/3Z Z/15Z 1 10, 2 5 φ, 1. R R/I a a

44 CHAPTER 3. 3.19 R R 4 3.19.1. R a a = bc = b c a a bc = a b a c a 3.19.2. R UFD R a 3.19.3. R UFD (1) a 1 R a 2 R (2) 3.19.4. (a) = ar R R 3.19.5. R Eulcid φ : R Z >0 a R, b R, q, r R a = bq + r, r = 0 φ(r) < φ(b). a modb b 3.19.6. Eulcid UFD Eulcid Eulcid UFD UFD :R ar + br cr : 1. d = 1, ±2, 3 Z[ d] Eulcid 2. R = Z[X] f R 2R + XR = fr

3.20. 45 3.20 R I, J I J, I + J = {x + y x I, y J} m IJ{ x i y i m N, x i I, y i J} i=1 IJ {xy x I, y J} I = ar, J = br = IJ = abr I = a 1 R + + a n R I a 1,..., a n a 1,..., a n I J b 1,..., b m IJ a i b j, i = 1,..., n; j = 1,..., m Z az bz a b az + bz = (a, b)z az bz = cz, c = l.c.m.[a, b] y 2 + 5 = x 3 Z[ 5] 2 3 = (1 + 5)(1 5) (1) Kummer Fermat (2 3) (5 7) = (2 7) (3 5) Z (1) 4 (2, 1 + 5), (2, 1 5), (3, 1 + 5), (3, 1 5) 4 Kummer (a 1,..., a n ) Z[ 5] 1 Z[ 5] 2 Z[ 5] I, I 3 I

46 CHAPTER 3. x y (y + 5)(y 5) = (x) 3 (y + 5) (y 5) (y + 5, y 5) 1 I (y + 5) = I 3, 2 I I = (a + b 5), (y + 5) = (a + b 5) 3, y + 5 = u(a + b 5) 3, u Z[ 5] u = ±1, y + 5 = (a + b 5) 3, 3.21 Z/pZ 3.21.1. n n 3.21.2. k G n m n x m = 1 k m G m abel k = Z/pZ p

Chapter 4 4.1 pot a p p r a p r a p r = pot p a (1) pot p ab = pot p a + pot p b (2) pot p (a + b) min(pot p a, pot p b) pot p a pot p b pot p Q n pot p ( a) = pot p a pot p m = pot pn pot p m a = p r n m r, m, n Z, (p, m) = (p, n) = 1 pot p a = r : a = 1 + 1 2 + + 1 20 m a m 20 p = 11, 13, 17 19 1 p 1 n, n = 1, 2,..., 20 pot px 0 x pot p 1 p = 1 (2) a a m pot p a = 1 pot p m = 1; p = 2 pot 2 1 16 = 4 1, 2,..., 20 n 16 pot 2 1 n 3 (2) pot 2 a = 4 47

48 CHAPTER 4. p = 3, 5, 7 2 0 1 i = 1 3 (1 + 1 2 + + 1 6 ) = 1 3 (2 + 9 20 ) pot 3 pot 5 pot 7 i=1,3 i 2 0 1 i = 1 pot 3a = 1 i=1,3 i pot 3 m = 1; 2 0 1 i = 1 5 (1 + 1 2 + 1 3 + 1 4 ) = 1 5 (5 4 + 5 6 ) = 1 4 + 1 6 i=1,5 i 2 0 1 i 0 pot 5a 0 i=1,5 i pot 3 m = 0; 2 0 1 i = 1 7 (1 + 1 2 ) = 1 7 3 2 ) i=1,7 i 2 0 1 i = 1 pot 7a = 1 i=1,7 i pot 7 m = 1; a = 2 4 3 7 11 13 17 19 2 1 + 1 2 + + 1 k k 4.1.1. p n pot p n! = [ n p ] + [ n p 2 ] + m = [ n p ] n! = 1 p 2p mp (mp + 1) n pot p n! = pot p (p m m!) = m + pot p m! [ n ij ] = [ [ n i ] j ] 4.1.2. p n A(n, p) n p pot p n! = n A(n, p) p 1

4.1. POT 49 m + m A(m, p) p 1 = n A(n, p)? p 1 p n = pm + a 0 A(n, p) = a 0 + A(m, p) pot p Q p p pot p a, a 0 a p = 0, a = 0 (1) ab p = a p b p (2) a + b p max( a p, b p ) (3) a p 0 a = 0 F (1) xy = x y (2) x + y x + y (3) x F x 0 x = 0 Kauchy 1 2 a > 0 x 1 = x a 2 F E F E F Kauchy 4.1.3. Q p p 4.1.4. ( ) x Q p. x p = 1 p (1) a Q p a p < 1 = a = 0 (2) a Z p x p x < 1 = a = 0 Q p-adic Q p p-adic p-adic Q p x x = a i p i, a i = 0, 1,..., p 1 i=m

50 CHAPTER 4. m a m 0. x p = p m ord p x = m i=m a ip i i=m b ip i p Q p Q 3 adic 1 + 3 + 3 2 + = 1 1 3 = 1 2 3 3 < 1 a n i=m a ip i Z p = {x Q p x p 1} = { i=1 a ip i, a i = 0, 1,..., p 1} Z p p-adic a, b Z p a b a b (mod p ) Q p 4.2 Euler µ(n) 1, n = 1 µ(n) = 0, n ( 1) r, n r 4.2.1. 1, n = 1 µ(d) = 0, n > 1 d n n > 1 n = p l 1 1 p lr r µ(d) = d n d p 1 p r µ(d) = r ( ) p ( 1) i = 0 i i=0 Euler φ(n) : (1) (m, n) = 1 φ(mn) = φ(m)φ(n) (2) φ(d) = n d n n (3) µ(n) φ(n) = µ(d) n d d n

4.3. DIRICHLET 51 4.3 Dirichlet f(n) g(n) f(n) g(n) = f(d)g( n d ) d n f(n) g(n) Dirichlet (f(n) g(n)) h(n) = f(n) (g(n) h(n)) f(a)g(b)h(c) abc=n 1, n = 1 I(n) = 0, n > 1 f(n) I(n) = f(n) I(n) * 4.3.1. f(n) f(n) f(1) 0 g(n) f(n) f(n) g(n) = I(n) f(1)g(1) = I(1) = 1 f(1) 0 g(n) f(n) g(n) = I(n) g(1) = 1/f(1) f(1)g(1) = 1 = I(1) k < n g(k) 0 = I(n) = f(0)g(n) + f(d)g( n d ) g(n) d n,d>1 Dirichlet I(n) 1 4.4 Dirichlet µ(n) e(n) = I(n), e(n) e(n) = 1 f(n) g(n) = f(n) e(n) = f(d) d n

52 CHAPTER 4. f(n) = g(n) µ(n) = d n g(d)µ( n d ) g(d)µ( n d ) g(n) d n φ(d) = n φ(n) = µ(d) n d d n d n : g(n) = f(d) = f(n) = g(d) µ( n d ) d n d n ζ n n n n ζn, j j = 1, 2,..., n; n ζn (j, j n) = 1 n φ n (x) = (x ζn) j j=1,(j,n)=1 x n 1 = d n φ d (x) φ n (x) = d n (x d 1) µ( n d ) 4.5 f(n) m, n f(mn) = f(m)f(n);f(n) m, n f(mn) = f(m)f(n) φ(n) µ(n) n a 4.5.1. Diricheli f(n) f(n)µ(n) f(n) f(n) f(p m+1 ) = f(p)f(p m )

4.6. 53 4.6 f(n) i=1 f(n) n f(n) Diricheli s Diricheli Diricheli Diricheli Diricheli f(n) n s i=1 4.6.1. π(n) n π(n) : (1) π(n) Eucilid ζ(s) = i=1 1 n s I(n) Diricheli s s > 1 ζ(s) = (1 + p s + p 2s + ) = (1 p s ) 1 p p p m=2 log ζ(s) = p p ms m ( log(1 p s )) = p m=1 p ms m = p p s + p m=2 p ms m (1) 0 < p m=2 p ms m < p m=2 p m = p p 2 1 p 1 = p 1 p(p 1) < 1 n(n 1) = 1 n=2 s 1 + (1) p p s Euler (2) π(n) n 0 (3) 1 8 n n log n < π(n) < 12 log n (4) (5) Riemann : ε > 0 C π(n) n log n < Cn 1 2 +ε π(n) p 1 = p π(n) n log n n log n = O(n 1 2 +ε )

54 CHAPTER 4. (3) = (2) (3) (4) (5) ζ(s) = (3) p i=1 1 n s n<p 2n p (2n)! n!n! r p,n p r 2n r n π(2n) π(n) < n<p 2n p p 2n p rp,n, ( ) 2n p rp,n (2n) π(2n) n p 2n n = 2 h 2 n ( ) 2n < 2 2n n n π(2n) π(n) < 2 2n, 2 n < (2n) π(2n) h(π(2 h+1 ) π(2 h )) < 2 h+1 (2) 2 h < (h + 1)π(2 h+1 ) (3) (2) (3) (2) (h + 1)π(2 h+1 ) hπ(2 h ) < 2 h+1 + π(2 h+1 ) < 3 2 2h+1 h = 0, 1,..., k (k + 1)π(2 k+1 ) < 3 2 k+1 n k 2 k n < 2 k+1 π(2 k+1 ) < 3 2 k+1 /(k + 1) π(n) π(2 k+1 ) < 3 2 k+1 /(k + 1) < 3(2n)/ log 2 n < 12 n log n e < 4 (3) π(n) π(2 k ) > 1 2 k 2 k > 1 4 n log 2 n > 1 n 8 log n m x a (mod m) a m (a, m) = 1 4.6.2. (a, m) = 1 x a (mod m)

4.6. 55 Diricheli Euler m = q a = 1 (Z/pZ) Z/(p 1)Z g 1, n ind g n = indn p 1 ω Z/(p 1)Z C 1 ω (Z/pZ) C ψ : n ω indn Z C χ ω : ψ(n), (n, q) = 1 χ ω (n) = 0, (n, q) > 1 χ ω (n) Diricheli L ω (s) = n=1 χ ω (n)n s = p (1 χ ω (p)p s ) 1 log L ω (s) = ( log(1 χ ω (p)p s )) = χ ω (p m )p ms m p q p q m=1 q 1 U q 1 ω j q 1, j 0 (mod p 1) = ω U q 1 0, j 0 (mod p 1) (4) (4) 1 p 1 ω U q 1 log L ω (s) = p m 1 (mod q) m=1 p m 1 (mod q) m=2 p ms m p ms m = p 1 (mod q) = O(1) p s + p m 1 (mod q) m=2 s 1 p 1 (mod q) p ω = 1 L 1 (s) = (1 q s )ζ(s), ω 1 L ω (s) s > 0 p ms m (5) L ω (1) 0, (6)

56 CHAPTER 4. (5) (6) ω L ω (1) = 0, L ω (1) = 0 ζ(s)l ω (s)l ω (s) 0, L ω (s) 0, ω U q 1 (5) L ω (s) > 1, ω U q 1 s Riemann s L 4.7 f(x 1,..., x n ) = 0 m f(x 1,..., x n ) 0 (mod m) 1 x 2 + y 2 = 3z 2 x, y, z p = 3 3 x 2 y 2 (mod 3), 1 3 p = 2 2 2 x 2 + y 2 + z 2 0 (mod 4), 3 4 3

4.8. FERMAT 57 2 9 x 2 + y 2 + z 2 = 9u ± 4 x 2 + y 2 + z 2 ±4 (mod 9) x 2 0, ±1 (mod 9) 3 y 2 = x 3 + (4b 1) 3 4a 2 a, b a 4t + 3 x x y 4 x 3 + (4b 1) 3 = (x + 4b 1)(x 2 (4b 1)x + (4b 1) 2 ) x 2 (4b 1)x + (4b 1) 2 ) 3 (mod 4) x 2 (4b 1)x + (4b 1) 2 ) p 3 (mod 4) p y 2 4a 2, a 0 (mod p) ( 1 p ) = 1 4.8 Fermat Fermat Fermat Fermat 4.8.1. x 2 + y 2 = z 2, 2 x x = 2ab y = a 2 b 2 z = a 2 + b 2 (a, b) = 1 a b Fermat 4 x 4 + y 4 = z 2 (x, y, z) z x, y, z x y z x 2 = 2ab (1) y 2 = a 2 b 2 (2) z = a 2 + b 2

58 CHAPTER 4. (a, b) = 1 a b (2) b y a b = 2uv (4) y = u 2 v 2 a = u 2 + v 2 (5) (u, v) = 1 u v (4) (5) (1) x 2 = 4uv(u 2 + v 2 ) u, v, u 2 + v 2 u = u 2 1, v = v1, 2 u 2 + v 2 = w 2 u 4 1 + v 4 1 = w 2 (u 1, v 1, w) w < z z x 4 y 4 = z 2 4.9 Catalan 1842 8 9 : m, n > 1 x m + 1 = y n m = 3, n = 2, x = 2, y = 3 x p + 1 = y q p, q p, q (1) p, q 2 (2) p, q (1) p = 2 Lebesque Gauss q = 2 x p + 1 = y 2 1) p = 3 1962 Selberg x p + 1 = y 4

4.9. 59 Catalan 4.9.1. 1) (x + 1, xp +1 x+1 ) > 1 (x + 1, xp +1 x+1 ) = 1 (x + 1, xp +1 x+1 ) = 1 p (x + 1, xp +1 x+1 ) = p y 2 = (x + 1) xp + 1 x + 1 x + 1 = py 2 1 2) x p + 1 x + 1 = py2 2 3) 1) x y (y + 1, y 1) = 1 y ± 1 p 2) p (1) p 3, 5, 7 (mod 8) x + 1 p (mod 8) 4) 1) jacobi 1 1 x 1 x p + 1 2 (mod x 1) p 5, 7 (mod 8) ( xp + 1 x 1 ) = ( 2 x 1 ) = ( 2 p 2 ) x 3 1 x p + 1 x + 1 x 2 + 1 (mod x 3 1) ( x + 1 x+1 1 x 3 ) = ( 1) 2 ( x3 1 1 x + 1 ) = ( 1 2 )( x + 1 x + 1 ) = ( 2 x + 1 ) = (2 p ) ( x2 + 1 x 3 1 ) = (x3 1 x 2 + 1 ) = ( x 1 x 2 + 1 ) = ( x + 1 x 2 + 1 ) = (x2 + 1 x + 1 ) = ( 2 x + 1 ) = (2 p ) p 3, 5, 7 ( xp + 1 x 3 1 ) = (2 p ) ( xp + 1 x 1 ) = 1 (xp + 1 x 3 1 ) = 1 (2) p 1 (mod 8) 3) E(a) = ( x)a 1 x 1,

60 CHAPTER 4. a E(a) = xa +1 x+1 E(a) Jacobi a < p a ( E(p) E(a) ) = 1 ( py2 2 E(a) ) = 1 m, n, t m n (mod t) ( x) m 1 ( x) n 1 (mod ( x) t 1) E(m) E(n) (mod E(t)) (E(m), E(n)) = E((m, n)) (m, n) = 1 (E(m), E(n)) = E(1) = 1 0 < a < p (a, p) = 1 p a 1 (mod a) a a 2 (mod a 2 ) a n 2 a n = 1 (mod a n 1 ) E(p) E(a 1 ) (mod E(a)) E(a) E(a 2 ) (mod E(a 1 ) E(a n 2 ) E(a n ) = 1 (mod E(a n 1 )) 4) x 1 (mod 8) E(p), E(a), E(a i ) 1 (mod 8) ( E(p) E(a) ) = (E(a 1) E(a) ) = ( E(a) E(a 1 ) ) = (E(a 2) E(a 1 ) ) = = ( E(1) E(a n 1 ) ) = 1 ( py2 2 E(a) ) = ( p E(a) ) = (E(a) p ) = (a p ) x 1 (mod p) 2) a ( a p ) = 1 x n + 1 = y n+1 (x, n + 1) = 1, n > 1

4.10. 61 4.10 p p p p p p-adic f(x 1,..., x n ) 1 f(x 1,..., x n ) = 0 p-adic Z p 2 f(x 1,..., x n ) 0 (mod p r ) r p f(x 1,..., x n ) 0 (mod p r ) r f(x 1,..., x n ) = 0 Z p p Z p 4.10.1. (Hasse-Minkowski) f(x 1,..., x n ) Q n f(x 1,..., x n ) = 0 Q Q p R Q Z Q p Z p R Q R Q Q p R Q