WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 42 | 43 || 45 | 46 |   ...   | 65 |

Целое число a называют квадратичным вычетом по модулю p, если a b2 (mod p) для некоторого целого числа b. В противном случае число a называют квадратичным невычетом.

31.34. Пусть p > 2 простое число. Докажите, что среди чисел 1, 2,..., p - 1 ровно половина квадратичных вычетов и ровно половина квадратичных невычетов по модулю p.

31.35. Пусть 1 a p-1, где p > 2 простое число. Докажите, что число a является квадратичным вычетом по модулю p тогда и только тогда, когда a(p-1)/2 1 (mod p) (Эйлер).

31.36. Пусть p > 2 простое число. Докажите, что число -1 является квадратичным вычетом по модулю p тогда и только тогда, когда p 1 (mod 4).

31.37. Пусть r это 2 или нечётное число, p1,.., pr различные.

pi простые числа вида 4k + 1. Предположим, что = -1 для всех pj i = j. Докажите, что уравнение x2 - dy2 = -1, где d = p1... pr, имеет решение в целых числах.

31.8. Квадратичный закон взаимности a Для простого числа p символ Лежандра определяется следуp ющим образом:

0, если a делится на p;

a = 1, если a квадратичный вычет;

p -1, если a квадратичный невычет.

366 Глава 31. Элементы теории чисел Символ Лежандра мы иногда будем обозначать (a/p).

Согласно задаче 31.35, если p нечётное простое число, то (a/p) a(p-1)/2 (mod p). Следовательно, (ab/p) = (a/p)(b/p) и 1 при p = 4k + 1;

-= p -1 при p = 4k + 3.

Квадратичный закон взаимности заключается в следующем. Пусть p и q различные нечётные простые числа. Тогда p-1 q-p q · 2 = (-1).

q p Кроме того, если p нечётное простое число, то = (-1)(p -1)/8.

p Впервые квадратичный закон взаимности был доказан Гауссом. Сейчас известно много разных доказательств квадратичного закона взаимности. Как правило, они используют какие-то интерпретации символа Лежандра. Мы приведём две такие интерпретации, принадлежащие Гауссу (задача 31.38) и Золотарёву (задача 31.39).

31.38. Пусть p нечётное простое число, а q натуральное число, p - не делящееся на p. Для каждого натурального числа l от 1 до p - запишем lq ±rl (mod p), где 1 rl. Пусть µ количество всех q встречающихся здесь минусов. Докажите, что = (-1)µ (Гаусс).

p 31.39. Пусть p нечётное простое число, a число, взаимно простое с p, и a,p : i ai (mod p) перестановка остатков от деления на p. Докажите, что тогда sgn a,p = (a/p), где sgn = 1 для чётной перестановки и sgn = -1 для нечётной перестановки. (Золотарёв) 31.40. Докажите квадратичный закон взаимности с помощью леммы Гаусса (задача 31.38) и тождества из задачи 5.29.

31.41. а) Докажите квадратичный закон взаимности с помощью задачи 31.39.

б) Пусть m нечётное простое число. Докажите, что = (-1)(m -1)/8.

m 31.42. Докажите квадратичный закон взаимности с помощью леммы Гаусса и тождества из задачи 11.31 (Эйзенштейн).

* * * Глава 31. Элементы теории чисел 31.43. Пусть p простое число. Докажите, что = 1 для p = p = 12k ± 1 и = -1 для p = 12k ± 5.

p -31.44. Пусть p простое число. Докажите, что = 1 для p = p -= 6k + 1 и = -1 для p = 6k - 1.

p 31.45. Докажите, что существует бесконечно много простых чисел вида 6k + 1.

31.46. а) Пусть p = 2n -1 простое число, причём p > 3. Докажите, что = -1.

p б) Пусть p = 2n + 1 простое число, причём p > 3. Докажите, что = -1.

p 31.47. Докажите, что 3n - 1 не делится на 2n - 1 при n > 1.

31.9. Гауссовы суммы Пусть p нечётное простое число, = e2i/p = cos(2/p) + + i sin(2/p). Для каждого целого числа a можно рассмотреть гауссову p-1 k k сумму ga = ak, где символ Лежандра. Ясно, что ga k=p p зависит только от остатка от деление a на p (и от самого числа p).

31.48. Докажите, что g0 = 0.

-31.49. Докажите, что g1 = p.

p 31.50. Докажите, что 2 4 cos - cos =, 5 5 2 4 6 sin + sin - sin =.

7 7 7 p-2 n(n + 1) 31.51. Докажите, что = -1.

n=p 31.52. Для каждого натурального n p - 2 пара (n, n + 1) имеет один из четырёх видов: (R, R), (N, N), (N, R), (R, N), где R означает 368 Глава 31. Элементы теории чисел вычет, а N невычет. Пусть RR, NN, NR, RN количества всех пар соответствующего вида.

а) Докажите, что RR + NN - RN - NR = 1.

б) Пусть = (-1)(p-1)/2. Докажите, что 1 RR + RN = (p - 2 - ), RR + NR = (p - 1) - 1, 2 1 NR + NN = (p - 2 + ), RN + NN = (p - 1).

2 в) Докажите, что p + 4 p p - RR = -, RN = -, NN = NR = +.

4 4 4 4 4 31.10. Суммы двух квадратов Здесь мы доказываем, что любое простое число p = 4k + 1 можно представить в виде суммы квадратов двух целых чисел. Различные подходы приведены в задачах 31.53–31.55. Другие доказательства этого утверждения можно найти в решении задачи 36.19 а) и на с. 496.

Представление простого числа p = 4k + 1 в виде суммы двух квадратов единственно (задача 31.56).

Напомним, что простое число p = 4k + 3 нельзя представить в виде суммы двух квадратов (задача 4.45 а). Кроме того, произведение двух чисел, представимых в виде суммы двух квадратов, само представимо в виде суммы двух квадратов (задача 5.11).

31.53. Пусть p = 4k + 1 простое число.

а) Докажите, что существует целое число x, для которого x2 + делится на p.

б) Докажите, что можно выбрать целые числа 0 r1, r2 < p и 0 s1, s2 < p так, что числа r1x+s1 и r2x+s2 будут давать одинаковые остатки при делении на p, причём (r1, s1) = (r2, s2).

в) Докажите, что p = (r1 - r2)2 + (s1 - s2)2.

31.54. Докажите, что любое простое число p = 4k + 1 можно представить в виде суммы квадратов двух целых чисел, воспользовавшись задачей 17.12.

31.55. Пусть p = 4k + 1 простое число.

а) Докажите, что уравнение x2 +y2 = mp имеет решение в натуральных числах x, y, m.

Глава 31. Элементы теории чисел б) Докажите, что если m > 1, то можно построить решение с меньшим m.

31.56. Докажите, что представление простого числа p = 4k+1 в виде суммы двух квадратов целых чисел единственно. (Мы не различаем представления p = x2 + y2, отличающиеся только перестановкой x и y или заменами знака x и y.) 31.11. Суммы четырёх квадратов 31.57. Докажите, что если каждое из чисел a и b является суммой четырёх квадратов целых чисел, то их произведение ab тоже является суммой четырёх квадратов целых чисел.

31.58. Пусть p нечётное простое число. Докажите, что существуют целые числа x, y и m, для которых 1 + x2 + y2 = mp, причём 0 < m < p.

31.59. Пусть p нечётное простое число.

а) Докажите, что можно выбрать натуральное число m < p и целые числа x1, x2, x3 и x4 так, что x2 + x2 + x2 + x2 = mp.

1 2 3 б) Докажите, что наименьшее такое m нечётно.

в) Докажите, что наименьшее такое m равно 1.

31.60. Докажите, что любое натуральное число можно представить в виде суммы четырёх квадратов целых чисел (Лагранж).

31.12. Первообразные корни по простому модулю Пусть p простое число, x натуральное число, не превосходящее p - 1. Тогда согласно малой теореме Ферма xp-1 1 (mod p). Наименьшее натуральное число d, для которого xd 1 (mod p), называют показателем, которому принадлежит x по модулю p.

Число x называют первообразным корнем по модулю p, если его показатель равен p - 1. Эквивалентное условие состоит в том, что числа x, x2,..., xp-1 дают разные остатки при делении на p. Первообразные корни существуют для любого простого числа p (задача 31.63).

31.61. Докажите, что показатель d делит число p - 1.

31.62. Докажите, что если xm 1 (mod p), то показатель d делит число m.

370 Глава 31. Элементы теории чисел 31.63. а) Докажите, что к каждому показателю d принадлежит не более (d) остатков от деления на p.

б) Докажите, что к каждому показателю d, делящему число p - 1, принадлежит ровно (d) остатков от деления на p.

в) Докажите, что для любого простого числа p существует ровно (p - 1) первообразных корней.

31.64. а) Дано натуральное число n 2. Докажите, что натуральное число d, для которого xd+1 x (mod n) для всех целых x, существует тогда и только тогда, когда n = p1... pk, где p1,..., pk попарно различные простые числа.

б) Пусть n = p1... pk, где p1,..., pk попарно различные простые числа. Докажите, что наименьшее натуральное число d, для которого xd+1 x (mod n) для всех целых x, равно НОК(p1 - 1,..., pk - 1).

31.65. Пусть p нечётное простое число.

а) Докажите, что нечётные простые делители числа ap-1 делят a-или имеют вид 2px + 1.

б) Докажите, что нечётные простые делители числа ap+1 делят a+или имеют вид 2px + 1.

31.66. Пусть p нечётное простое число. Докажите, что существует бесконечно много простых чисел вида 2px + 1.

n 31.67. Докажите, что все простые делители числа 22 +1 имеют вид 2n+1x + 1.

31.68. Докажите, что 3 является первообразным корнем по модулю простого числа p = 2n + 1, где n > 1.

31.69. Пусть p простое число и S = 1n + 2n +... + (p - 1)n.

Докажите, что -1 (mod p), если n делится на p - 1, S 0 (mod p), если n не делится на p - 1.

31.13. Первообразные корни по составному модулю Первообразные корни можно рассмотреть и для составного модуля m. Будем называть число x первообразным корнем по модулю m, если числа x, x2,..., x(m) это все различные остатки, взаимно простые с m. В серии задач 31.71–31.77 доказывается, что первообразный корень Глава 31. Элементы теории чисел по модулю m существует тогда и только тогда, когда m = 2, 4, p или 2p, где p нечётное простое число.

-31.70. Докажите, что (1 + km)m 1 (mod m) для любого m.

31.71. Пусть p простое число. Докажите, что первообразный корень по модулю p является также первообразным корнем по модулю p.

31.72. Пусть x первообразный корень по простому модулю p.

-Предположим, что xp (p-1) 1 (mod p), где 2. Докажите, что тогда x первообразный корень по модулю p.

31.73. Пусть x первообразный корень по нечётному простому модулю p. Докажите, что по крайней мере одно из чисел x и x+p является первообразным корнем по модулю p2.

31.74. Докажите, что если x первообразный корень по модулю p2, где p нечётное простое число, то x первообразный корень по модулю p для любого 2.

31.75. Пусть p нечётное простое число. Докажите, что для любого натурального существует первообразный корень по модулю 2p.

31.76. Докажите, что первообразный корень по модулю 2n существует тогда и только тогда, когда n 2.

31.77. Докажите, что если m это не число вида 2, 4, p или 2p, где p нечётное простое число, то первообразных корней по модулю m не существует.

31.14. Теорема Чебышёва о простых числах Пусть (n) количество простых чисел, не превосходящих n.

31.78. Докажите, что limn (n)/n = 0 (Эйлер).

2 n 31.79. Докажите, что < (n) при n > 200.

3 ln n n 31.80. Докажите, что (n) < 3 ln 2 при n > 55.

ln n Замечание. Чебышёв доказал, что для достаточно больших n выполняются более точные неравенства n n 0, 92129 < (n) < 1, 10555.

ln n ln n 372 Глава 31. Элементы теории чисел Решения 31.1. П е р в о е р е ш е н и е. Согласно задаче 4.62 набор остатков от деления на p чисел a, 2a,..., (p - 1)a совпадает с набором 1, 2,..., p - 1. Значит, ap-1 ·1·2... (p-1) 1·2... (p-1) (mod p). Число b = 1·2... (p-1) не делится на p, поэтому ap-1 1 (mod p). Чтобы доказать это, нужно умножить обе части равенства на число b, для которого bb 1 (mod p).

В т о р о е р е ш е н и е. Покажем, что для любого натурального n число np - n делится на p. Применим индукцию по n. При n = 1 утверждение очевидно. Предположим, что np - n делится на p. Тогда число (n + 1)p - (n + p p p + 1) = np-1 + np-2 +... + n тоже делится на p, поскольку все 1 2 p - p числа, где 1 k p - 1, делятся на p (задача 14.30).

k Если число n не делится на p, то из того, что np - n = n(np-1 - 1) делится на p, следует, что np-1 - 1 делится на p.

31.2. Предположим, что одно из чисел a и b не делится на p. Тогда другое число тоже не делится на p. Поэтому согласно малой теореме Ферма ap-1 (mod p) и bp-1 1 (mod p). Значит, ap-1 + bp-1 2 (mod p). С другой стороны, число ap-1 + bp-1 = a4k+2 + b4k+2 = (a2)2k+1 + (b2)2k+1 делится на a2 + b2, поэтому оно делится на p.

31.3. Предположим, что p1,..., pr все различные простые числа вида 4k+1. Рассмотрим число (2p1... pr)2+1. Оно нечётно, поэтому все его простые делители имеют вид 4k ±1. Согласно задаче 31.2 у этого числа не может быть простых делителей вида 4k-1. Остаётся заметить, что рассматриваемое число не делится на p1,..., pr.

31.4. а) Предположим, что 2p 1 (mod q), где q простое число. Ясно, что q = 2. Если q-1 не делится на p, то наибольший общий делитель чисел q- и p равен 1, поэтому существуют целые числа a и b, для которых ap+b(q-1) = = 1 (см. с. 40). Согласно малой теореме Ферма 2q-1 1 (mod q). Поэтому 2 2ap+b(q-1) (2p)a(2q-1)b 1 (mod q). Приходим к противоречию.

б) О т в е т: 211 - 1 = 23 · 89.

31.5. Число 2341 -2 = 2(2340 -2) = 2 (210)34 -1 делится на 210 -1 = 1023.

Далее, 1023 = 3 · 341.

31.6. По условию 2n 2 = na для некоторого натурального a. Поэтому n n 22 -1 - 2 = 2 22 -2 - 1 = 2(2na - 1). Это число делится на 2n - 1.

31.7. а) Среди чисел 1, 2,..., pn -1 на p делятся pn-1 -1 чисел, а именно, числа p, 2p,..., p(pn-1 - 1). Поэтому (pn) = pn - 1 - (pn-1 - 1) = pn - pn-1.

б) Числа m и n взаимно простые, поэтому существуют целые числа u и v, для которых um + vn = 1 (эти числа можно найти с помощью алгоритма Евклида). Пусть a и b некоторые остатки от деления на m и n, т.е.

0 a m - 1 и 0 b n - 1. Сопоставим паре (a, b) число c, которое является остатком от деления числа avn + bum на mn. Ясно, что c avn a Глава 31. Элементы теории чисел (mod m) и c bum b (mod n). Поэтому, в частности, разным парам (a, b) сопоставляются разные числа c. Мы получили взаимно однозначное отображение остатков от деления на m и n на остатки от деления на mn. При этом НОД(c, m) = НОД(a(1-um)+bum, m) = НОД(a, m) и НОД(c, n) = НОД(b, n).

Поэтому числа c и mn взаимно простые тогда и только тогда, когда числа a и m взаимно простые и числа b и n тоже взаимно простые.

Замечание. Используя задачи а) и б), легко получить формулу для (n), где n = pa1... pak. Другое доказательство этой формулы приведено в реше1 k нии задачи 14.36.

31.8. Пусть a1, a2,..., a(n) все числа от 1 до n - 1, которые взаимно просты с n. Сопоставим числу ai остаток от деления числа aai на n. Число aai взаимно просто с n, поэтому мы снова получим одно из чисел a1, a2,..., a(n). При этом число a(ai - aj) при i = j не может делиться на n. Значит, мы получаем некоторую перестановку чисел a1, a2,..., a(n). Поэтому a(n)a1... a(n) a1... a(n) (mod n). (1) Умножение на число b = a1... a(n) тоже задаёт некоторую перестановку чисел a1, a2,..., a(n). Поэтому bb 1 (mod n) для некоторого числа b = ai.

Умножив обе части сравнения (1) на b, получим требуемое.

31.9. Согласно теореме Эйлера (задача 31.8) можно положить m = (n).

Pages:     | 1 |   ...   | 42 | 43 || 45 | 46 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.