Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
31.42. Пусть lq ≡ e l r l (mod p), где e l = ±1 и 1 6 r l 6 p − 1 2 . Тогда sin 2 p lq p = e l sin 2 p r l p . Перемножим такие равенства для l = 1, 2, . . . . . . , p − 1 2 . При доказательстве леммы Гаусса было показано, что набор чисел r 1 , . . . , совпадает с набором 1, 2, . . . , p − 1 Поэтому после сокращения получаем. . Воспользуемся тождеством из задачи 11.31 для 2k + 1 = q и f = = sin 2 p l p . В результате получим 2 p l p − sin 2 2 p m q ” = = (−4) (p −1)(q−1)/4 Y l,m “ sin 2 2 p l p − sin 2 2 p m q ” Глава 31. Элементы теории чисел Аналогично “ p q ” = (−4) (p −1)(q−1)/4 Y l,m “ sin 2 2 p m q − sin 2 Таким образом, чтобы получить из выражения для “ p q ” выра- жение для, нужно поменять знаку каждого из 1 2 · q − 1 сомножителей. Следовательно (−1) (p −1)(q−1)/4 “ q p ” 31.43. Согласно квадратичному закону взаимности (−1) (p −1)/2 . Ясно также, что 3 ” = ±1. Поэтому для p = 12k ± получаем ± “ 3 p ” = ±1, а для p = 12k ± 5 получаем ∓ “ 3 p ” = ±1. 31.44. Ясно, что (−1) (p −1)/2 “ 3 p ” . Далее 1 для p = 12k + 1 и p = 12k + 5, (−1) (p −1)/2 = −1 для 12k − 1 и p = 12k − 5. Воспользовавшись результатом задачи, получим требуемое. Предположим, что существует лишь конечное число простых чисел вида 6k + 1. Пусть N — их произведение, а p — простой делитель числа 4N 2 + 3. Число p нечётно итак как N не делится на 3. Поскольку (2N) 2 ≡−3 (mod p), то 1. Согласно задаче 31.44 число p имеет вид 6k + 1. Нов таком случае число должно делиться на p. Итак, числа N и 4N 2 + 3 делятся на p. Следовательно делится нате. Приходим к противоречию. а) Ясно, что p ≡ −1 (mod 4). Кроме того, p ≡ 1 (mod Действительно, n нечётно, поскольку число 2 2m − 1 делится 2 m − а потому не может быть простым при m > 1. Атак как 2 2 ≡ ≡ 1 (mod 3), то 2 n − 1 ≡ 1 (mod 3) для любого нечётного n. В результате получаем, что p ≡ 7 (mod 12). Остаётся воспользоваться результатом задачи б) Ясно, что p ≡ 1 (mod 4). Кроме того, p ≡ −1 (mod 3). Действительно чётно, поскольку иначе число 2 n + 1 делится на. Атак как 2 2 ≡1 (mod 3), то 2 n + 1≡−1 (mod 3) для любого чётного n. В результате получаем, что p ≡ 5 (mod 12). Остаётся воспользоваться результатом задачи 31.43. 31.47. Если n = 2m, то 2 n − 1 делится на 2 2 − 1 = 3. Но число не делится на 3. Поэтому остаётся рассмотреть случай, когда 2m + 1. Поскольку 2 4 ≡ 2 2 (mod 12), то 2 2m ≡ 4 (mod 12), а зна- Решения задач 423 чит, 2 n − 1 ≡ 7 (mod 12). Любое простое число p > 3 при делении на 12 даёт остаток ±1 или ±5. У числа 2 n − 1 должен быть простой делитель p > 3, дающий при делении на 12 остаток Предположим, что 3 n − 1 делится на 2 n − 1. Тогда, в частности 1 делится на p. Следовательно, 3 2(m+1) = 3 n +1 ≡ 3 (mod p). Таким образом 1. Но это противоречит квадратичному закону взаимности (см. задачу 31.43). 31.48. Ясно, что g 0 = p −1 P k =1 “ k p ” . Половина чисел от 1 до p − являются квадратичными вычетами, а остальные — невычетами. 31.49. Ясно, что При фиксированном l отображение k 7→ kl является перестановкой остатков отделения на p, поэтому X l e l(k +1) = “ −1 p ” (p − 1) + поскольку при фиксированном k 6= −1 остатки отделения чисел+ 1) на p образуют набор 1, 2, . . . , p − 1 и e + e 2 + . . . + e p −1 = Ясно также, что g 0 = 0. 31.50. Запишем тождество g 2 1 = “ −1 p ” p для p = 5 и 7. Для p = получим g 1 = ± √ 5, а для p = 7 получим g 1 = ±i √ 7. Легко видеть, что это и есть требуемые тождества с точностью до знака. Знак в обоих случаях легко выясняется. Для каждого натурального числа n 6 p − 1 существует единственное натуральное число n 6 p − 1, для которого nn ≡ ≡ 1 (mod p). При этом p − 1 = p − 1. Поэтому когда n пробегает числа от 1 до p − 2, n тоже пробегает числа от 1 до p − 2 (в другом порядке. Ясно также, что n 2 (1 + n) ≡ n 2 + n ≡ n(n + 1) (mod поэтому + 1) p ” = p −2 X n =1 “ n 2 (1 + n) p ” = p −2 X n =1 “ 1 + n p ” = g 0 − “ 1 p ” = поскольку g 0 = 0 (задача 31.48). Глава 31. Элементы теории чисел. а) Ясно, что + 1 p ” = 1 в случаях RR и NN, а в случаях и RN это произведение равно −1. Следовательно, RR + + NN − RN − NR = p −2 P n =1 “ n(n + 1) p ” . Остаётся воспользоваться результатом задачи б) Количество вычетов среди чисел 2, 3, . . . , p−1 равно а количество невычетов равно RN + NN. Среди чисел 1, 2, 3, . . . . . . , p − 1 вычетов и невычетов поровну. Кроме того, 1 — вычет. Поэтому RN + NN = 1 2 (p − 1) и RR + NR = 1 2 (p − 1) − Количество вычетов среди чисел 1, 2, . . . , p − 2 равно RR + а количество невычетов равно NR + NN. Кроме того 1 p ” = = “ −1 p ” = e . Поэтому RR+RN= 1 2 (p −2− e ) ив) Сложим равенства RR+NN−RN−NR=1, RR+RN= 1 и NR + NN = 1 2 (p −2+ e ). В результате получим RR + NN = 1 Вычитая из равенства RR + RN = 1 2 (p − 2 − e ) равенство RN + NN = = 1 2 (p − 1), получаем RR − NN = − 1 2 ( e + 1). Следовательно, RR = = p 4 − e + 4 и NN = p 4 + e − 2 4 . После этого легко находим RN и NR = p 4 + e − 2 Замечание. Равенства из задачи б) не являются независимыми сумма равенств с равна RR + NN + RN + NR = p − 2; сумма равенств без та же самая. а) Непосредственно следует из задачи б) Если целое число r удовлетворяет неравенствам 0 6 r < то r может принимать больше √p различных значений (поскольку может принимать значение 0). Таким образом, количество различных допустимых пар (r, s) больше √p · √p = p. Следовательно, для каких-то двух пар числа rx + s дают одинаковые остатки при делении на в) Пусть r 1 x +s 1 ≡r 2 x +s 2 (mod p), те Положим u = |r 1 − r 2 | и v = |s 1 − s 2 |. По построению числа u и v не могут быть одновременно равны нулю кроме того, u, v < √p. Так как ux ≡ ±v (mod p), то u 2 x 2 ≡ v 2 (mod p). Но x 2 + 1 ≡ 0 (mod p), поэтому. С другой стороны+ v 2 < ( √ p) 2 + ( √ p) 2 = 2p, поэтому u 2 + v 2 = p. Решения задач. Согласно задаче 31.36 можно выбрать натуральное число так, что q 2 ≡ −1 (mod p). Рассмотрим число a = q/p. Пусть. Согласно задаче 17.12 можно выбрать натуральное число < C = √ p и целое число y так, что 6 1/C, те Положим r =xq−yp. Тогда 1 √ p , поэтому |r|6 √ p. Следовательно. С другой стороны, x 2 + r 2 ≡ x 2 + x 2 q 2 ≡ ≡ x 2 (1 + q 2 ) ≡ 0 (mod p). Поэтому x 2 + r 2 = p. 31.55. а) Согласно задаче 31.36 можно выбрать натуральное число x так, что x 2 ≡ −1 (mod p), те. Таким образом, мы нашли требуемое решение, даже с дополнительным условием б) Пусть m 0 — наименьшее натуральное число, для которого имеет место равенство+ y 2 = К x и y можно добавлять кратные p, поэтому можно считать, что и |y|<p/2. Следовательно, x 2 +y 2 < p 2 /2, а значит, Пусть m 0 > 1. Предположим, что делит x. Тогда не делит, поскольку иначе 0 = m 0 p m 2 0 = p m 0 — целое число, а это противоречит тому, что 1 < Выберем целые числа c итак, чтобы числа x 1 = x − и y 1 = y удовлетворяли неравенствами Как только что было доказано, числа и не могут быть равны нулю одновременно. Таким образом, 0 < x 2 1 + y 2 1 6 2 m 2 0 4 = m 0 и x 2 1 + y 2 1 ≡ x 2 + y 2 ≡ 0 (mod m 0 ). Следовательно 1 + y 2 1 = где 0 < m 1 6 m 0 /2. Перемножим равенства (1) и (2). В результате получим 0 m 1 p = (x 2 + y 2 )(x 2 1 + y 2 1 ) = (xx 1 + yy 1 ) 2 + (xy 1 − При этом+ yy 1 = x(x − cm 0 ) + y(y − dm 0 ) = x 2 + y 2 − m 0 (cx + dy) = = m 0 (p − cx − dy), xy 1 − yx 1 = x(y − dm 0 ) − y(x − cm 0 ) = m 0 (cy − Таким образом, m 2 0 m 1 p = m 2 0 (X 2 + Y 2 ), где X = p − cx − dy и Y = = cy − dx. Сокращая на m 2 0 , получаем X 2 + Y 2 = m 1 p, причём 0 < m 1 6 m 0 /2. Глава 31. Элементы теории чисел. Предположим, что p = x 2 + y 2 = a 2 + b 2 . Сравнение z 2 ≡ ≡ −1 (mod p) имеет ровно два решения z ≡ ±h (mod p). Поэтому ±hy (mod p) и a ≡ ±hb (mod p). У чисел x и a можно поменять знаки, поэтому будем считать, что x ≡ hy (mod p) и a ≡ hb (mod Тогда xb ≡ ya (mod Ясно, что (x 2 + y 2 )(a 2 + b 2 ) = (xa + yb) 2 + (xb − Но xb − ya ≡ 0 (mod p), поэтому (xa + делится на p 2 . Итак, обе части равенства (1) можно сократить на p 2 . В результате получим представление числа 1 в виде суммы двух квадратов целых чисел. Такое представление единственно, поэтому либо xa + yb = 0, либо. Числа x и y взаимно простые, числа a и b тоже взаимно простые. Поэтому если xb = ya, то либо x = a и y = b, либо x = и y = −b. Если же xa = −yb, то либо x = b и y = −a, либо x = и y = a. 31.57. Пусть a = x 2 1 + x 2 2 + x 2 3 + x 2 и b = y 2 1 + y 2 2 + y 2 3 + y 2 4 . Несложно проверить, что ab = z 2 1 + z 2 2 + z 2 3 + z 2 4 , где x 1 y 1 + x 2 y 2 + x 3 y 3 + x 4 y 4 , z 2 = x 1 y 2 − x 2 y 1 + x 3 y 4 − x 4 y 3 , z 3 = x 1 y 3 − x 3 y 1 + x 4 y 2 − x 2 y 4 , z 4 = x 1 y 4 − x 4 y 1 + x 2 y 3 − x 3 y 2 31.58. Числа x 2 , где x — целое число и 06 x6 p − 1 2 , дают разные остатки при делении на p. Действительно, если x 2 1 ≡ x 2 2 (mod p), то x 2 ≡ 0 (mod p). Нов рассматриваемой ситуации 0 < x 1 + Аналогично числа −1 − y 2 , где 0 6 y 6 p − 1 2 , дают разные остатки при делении на p. Количество чисел в обеих группах равно+ 1, поэтому какие-то два числа дают одинаковые остатки при делении на p. Эти числа должны быть из разных групп. Таким образом, x 2 ≡ −1 − y 2 (mod p), те, причём x 2 , y 2 6 “ p − 1 2 ” 2 < “ p 2 ” 2 . Следовательно, 1 + x 2 + y 2 < 1 + а значит, 0 < m < p. 31.59. а) Непосредственно следует из задачи 31.58: можно положить и x 4 = б) Предположим, что число x 2 1 + x 2 2 + x 2 3 + x 2 4 чётно. Тогда количество нечётных чисел среди x 1 , x 2 , и x 4 чётно. Поэтому можно считать, что числа и одной чётности и числа и тоже Решения задач 427 одной чётности. Тогда тождество x 2 2 ” 2 + “ x 1 + x 2 2 ” 2 + “ x 3 − x 4 2 ” 2 + “ x 3 + x 4 показывает, что чётное число m можно заменить на меньшее число в) Предположим, что m 0 — наименьшее из рассматриваемых чисел m, причём m 0 6= 1. Согласно задаче б) число m 0 нечётно. Поэтому каждое число можно представить в виде x i = m 0 b i + где |y i | < m 0 /2. Действительно, если r i — остаток отделения на m 0 , то одно из чисел или m 0 − меньше Числа x 1 , x 2 , и не могут все делиться на m 0 , поскольку иначе m 0 p = x 2 1 + x 2 2 + x 2 3 + x 2 делится на m 0 , а значит, p делится на m 0 . Но 1 < m 0 < p. Следовательно, хотя бы одно из чисел y 1 , и отлично от нуля. Таким образом < y 2 1 + y 2 2 + y 2 3 + y 2 4 < 4 “ 1 2 m 0 ” 2 = m 2 Кроме того, y i ≡ x i (mod m 0 ), поэтому 1 + y 2 2 + y 2 3 + y 2 4 ≡ x 2 1 + x 2 2 + x 2 3 + x 2 4 = m 0 p ≡ 0 (mod Из (1) и (2) получаем, что y 2 1 + y 2 2 + y 2 3 + y 2 4 = m 0 m 1 , где 0 < Умножим число x 2 1 + x 2 2 + x 2 3 + x 2 4 = m 0 p на y 2 1 + y 2 2 + y 2 3 + y 2 4 = и воспользуемся тождеством из решения задачи 31.57. В результате получим равенство вида z 2 1 + z 2 2 + z 2 3 + z 2 4 = m 2 0 m 1 p. Несложно проверить, что каждое из чисел z 1 , z 2 , z 3 , делится на m 0 . Действительно Для и доказательство аналогично. Положим t i = z i /m 0 . Тогда t 2 1 + t 2 2 + t 2 3 + t 2 4 = m 1 p, где 0 < Это противоречит предположению о том, что число наименьшее. Согласно задаче 31.59 любое нечётное простое число можно представить в виде суммы четырёх квадратов целых чисел. Число 2 можно представить так 2 = 1 2 + 1 2 + 0 2 + 0 2 . Остаётся воспользоваться результатом задачи 31.57. |