(3) 25 7 17 1 φ n φ(n) n k n. k < n k n k φ(n). 10 1 10, 3 10, 7 10, 9 10 φ(10) = 4. φ(100) = 40, φ(1000) = 400. 100.,. φ.. 1. n p p p φ(p) = p 1. 2. n p 2 p p 2 φ(p 2 ) = p 2 p = p(p 1). 3. φ(p e ) = p e 1 (p 1). 4. p, q pq. p n/p = q, q n/q = p. pq pq. pq. φ(pq) = pq (p + q 1) = (p 1)(q 1). n, m φ(nm) = φ(n)φ(m).. φ(n) n p e φ(p e ). p e 1 (p 1). e = φ(n),.. [2,2] 2 2. 1
1: n n e = φ(n) e 2 [2] 1 [1] 3 [3] 2 [2] 4 [2,2] 2 [2] 5 [5] 4 [2,2] 6 [2,3] 2 [2] 7 [7] 6 [2,3] 8 [2,2,2] 4 [2,2] 9 [3,3] 6 [2,3] 10 [2,5] 4 [2,2] 11 [11] 10 [2,5] 12 [2,2,3] 4 [2,2] 13 [13] 12 [2,2,3] 14 [2,7] 6 [2,3] 15 [3,5] 8 [2,2,2] 16 [2,2,2,2] 8 [2,2,2] 17 [17] 16 [2,2,2,2] 18 [2,3,3] 6 [2,3] 19 [19] 18 [2,3,3] 20 [2,2,5] 8 [2,2,2] 21 [3,7] 12 [2,2,3] 22 [2,11] 10 [2,5] 23 [23] 22 [2,11] 24 [2,2,2,3] 8 [2,2,2] 25 [5,5] 20 [2,2,5] 26 [2,13] 12 [2,2,3] 27 [3,3,3] 18 [2,3,3] 28 [2,2,7] 12 [2,2,3] 29 [29] 28 [2,2,7] 30 [2,3,5] 8 [2,2,2],. φ(2) = 1, φ(3) = φ(4) = φ(6) = 2. 2
2.,......,,.. 3
4
1. φ(2) = 1. ( ) 2. 14, 26,34. 14 = 2 7, 26 = 2 13, 34 = 2 17.,m = 2 p(p ). n φ(n). n 2. P, Q P 1 Q 1 2 4. φ(n) = 2 p.,2 2 s n φ(n) = 2 p s = 1. a) n = P e b) n = 2P e. a). n = P e, P > 2 φ(n) = (P 1)P e 1, (P 1)P e 1 = 2p (1). e = 1, 2p = P 1 (2). e = 2, 2 = P 1, P = p = 3. (1). P = 2p + 1 2p + 1.. 1 p 2p + 1 2p. p = 7, 13, 17 2p + 1 14,26,34 (2). n = 9 φ(9) = 6. p = 3 2p = 6. b). n = 2P e, P > 2 φ(n) = φ(p e ). 5
2.1 N φ (m) φ(n) = m n. N φ (m) > 1,. 3 ( 1922 ), Wikipedia( ). 1 N < 10 37 N 2 Victor Klee N < 10 400 1947 3 Schlafly Wagon N < 10 107 4 Kelvin Ford N < 10 1010 1998 4 2... N φ (m) = 2 m. N φ (10) = 2. N φ (m) = 2 10 = 2 5, 22 = 2 11, 28 = 2 2 7, 30 = 2 3 5, 46 = 2 23, 54 = 2 3 3, 56 = 2 3 7.. 10 = 2 5. 5 11 11 = 2 5 + 1. 4.1 p, q q = 2p+1. p = 5, q = 11; p = 11, q = 23;p = 23, q = 47.. 1 1 Sophie Germain 6
. q, m,. 4.2 2 Ribenboim (, 1995) 2 m m = 2 3 6k+1. k > 0. M = m + 1. k = 0 M = 7 N φ (7) = 4. N φ (m) = 2. k > 0 M = 2 3 6k+1 + 1.,.,. 7
, M 7. mod7. 3 2 = 9 2 mod 7 3 3 2 3 1 mod 7. 3 6 1 mod 7 M = 2 3 6k+1 + 1 2 3 6k 3 + 1 6 + 1 0 mod 7. M 7 k > 0. 4.3 N φ (m) = 2 m = 2 3 6k+1 φ(n) = m n., n φ(n) = n 1 = m n = m + 1. M = m + 1. N = 3 6k+2 φ(n) = 3 6k+2 3 6k+1 = 2 3 6k+1 = m. N 2 φ(2 N) = φ(n) = 2 3 6k+1 = m., φ(3 6k+2 ) = φ(2 3 6k+2 ) = m., φ(n) = m n. 1). n p φ(p) = p 1.,p = 2 3 6k+1 + 1 = M, M. 2).n φ(n) = 2 3 6k+1 P n = P e, n = 2P e. i). n = P e φ(n) = (P 1)P e 1, e > 1. (P 1)P e 1 = 2 3 6k+1. P 1 = 2, e 1 = 6k + 1. P = 3, e = 6k + 2. n = 3 6k+2. ii). n = 2P e φ(n) = (P 1)P e 1. n = 2 3 6k+2. m = 2 3 6k+1. 5 1. N φ (m) = 3 m.. m = 2. : N φ (m) = 3 2 m. 2. N φ (m) = 3 m.. m = 8. : N φ (m) = 5 8 m. 3. 16,. 8
14,26,34,50,62,68,74,76,86,90,94,98,114 4. p 4p.. 26.,. 3,4. 2012.,. 9
2: 1 n n e = φ(n) e 2 [2] 1 [1] 3 [3] 2 [2] 4 [2,2] 2 [2] 6 [2,3] 2 [2] 5 [5] 4 [2,2] 8 [2,2,2] 4 [2,2] 10 [2,5] 4 [2,2] 12 [2,2,3] 4 [2,2] 7 [7] 6 [2,3] 9 [3,3] 6 [2,3] 14 [2,7] 6 [2,3] 18 [2,3,3] 6 [2,3] 15 [3,5] 8 [2,2,2] 16 [2,2,2,2] 8 [2,2,2] 20 [2,2,5] 8 [2,2,2] 24 [2,2,2,3] 8 [2,2,2] 30 [2,3,5] 8 [2,2,2] 11 [11] 10 [2,5] 22 [2,11] 10 [2,5] 13 [13] 12 [2,2,3] 21 [3,7] 12 [2,2,3] 26 [2,13] 12 [2,2,3] 28 [2,2,7] 12 [2,2,3] 36 [2,2,3,3] 12 [2,2,3] 42 [2,3,7] 12 [2,2,3] 17 [17] 16 [2,2,2,2] 32 [2,2,2,2,2] 16 [2,2,2,2] 34 [2,17] 16 [2,2,2,2] 40 [2,2,2,5] 16 [2,2,2,2] 48 [2,2,2,2,3] 16 [2,2,2,2] 60 [2,2,3,5] 16 [2,2,2,2] 19 [19] 18 [2,3,3] 27 [3,3,3] 18 [2,3,3] 38 [2,19] 18 [2,3,3] 54 [2,3,3,3] 18 [2,3,3] 25 [5,5] 20 [2,2,5] 33 [3,11] 20 [2,2,5] 44 [2,2,11] 20 [2,2,5] 50 [2,5,5] 20 [2,2,5] 66 [2,3,11] 20 [2,2,5] 23 [23] 22 [2,11] 46 [2,23] 10 22 [2,11] 35 [5,7] 24 [2,2,2,3] 39 [3,13] 24 [2,2,2,3] 45 [3,3,5] 24 [2,2,2,3] 52 [2,2,13] 24 [2,2,2,3]
3: M = 2 3 6k+1 + 1 k m = 2 3 6k+1 + 1 M = m + 1, M 0 6 7 [7] 1 4374 4375 [5,5,5,5,7] 2 3188646 3188647 [7,11,41411] 3 2324522934 2324522935 [5,7,587,113143] 11