WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 44 | 45 || 47 | 48 |   ...   | 65 |

380 Глава 31. Элементы теории чисел p - 31.40. Пусть lq lrl (mod p), где l = ±1 и 1 rl. Докажем, что l = (-1)[2lq/p]. Действительно, l = 1 тогда и только тогда, когда {lq/p} < 1/2. С другой стороны, для любого положительного число [2] = = [2[] + 2{}] = 2[] + [2{}] чётно тогда и только тогда, когда {} < 1/2.

Полагая = {lq/p}, получаем, что число [2ql/p] чётно тогда и только тогда, когда {lq/p} < 1/2. Итак, лемму Гаусса можно записать следующим образом:

(p-1)/q = (-1)m, где m = [2lq/p].

l=p Для любого нечётного числа a число a + p чётно, поэтому 2 a 2a 4 (a + p)/2 (a + p)/= = = = (-1)s, (1) p p p p p p где (p-1)/2 (p-1)/2 (p-1)/ (a + p)l al s = = + l = p p l=1 l=1 l= (p-1)/ al p2 - = +.

p l= 2 В частности, при a = 1 получаем = (-1)(p -1)/8. Подставив это выражеp (p-1)/2 al a ние в (1), после сокращения получим = (-1)M, где M =.

l=p p Пусть p и q различные нечётные простые числа. Тогда (p-1)/2 ql (q-1)/2 pl + q p l=1 l=p q = (-1) p q Остаётся заметить, что (p-1)/2 (q-1)/ ql pl p - 1 q - + = · p q 2 l=1 l=согласно задаче 5.29.

31.41. а) Пусть P = {0, 1,..., pq - 1} и P = { (a, b) | 0 a < p, 0 b < q}.

Согласно китайской теореме об остатках отображение c c = (c (mod p), c (mod q)) является взаимно однозначным отображением P на P.

Рассмотрим отображения µ, : P P, заданные формулами µ(a, b) = = a + pb и (a, b) = qa + b. Ясно, что µ(a, b) = (a, a + pb (mod q)), поэтому отображение µ переставляет элементы вида (a0, b), где a фиксировано. Сле 0 p p p довательно, µ перестановка множества P и sgn µ = =. Аналоq q q гично sgn =.

p Рассмотрим теперь на множестве P перестановку -1µ : qa + b a + + pb. Знак этой перестановки равен (-1)k, где k количество пар элементов Глава 31. Элементы теории чисел множества P, для которых выполняются неравенства qa + b > qa + b и a + + pb < a + pb. По условию |b - b | < q и |a - a | < p, поэтому приходим к q p следующим неравенствам: a > a и b < b. Таким образом, k = = 2 p - 1 q - = ·. В итоге получаем 2 p-1 q-p q · 2 = sgn µ sgn = sgn -1µ = (-1).

q p б) При m = 3 требуемое равенство легко проверяется. Предположим, что m 3 нечётное натуральное число, для которого выполняется требуемое равенство. Тогда m+1 m-1 m+2 -1 m m + · 2 2 = = (-1) (-1) = m + 2 m + 2 m + 2 m (m+2)2-m+1 m+1 m2-2 2 8 = (-1) = (-1) (-1) = (-1).

m p - 31.42. Пусть lq lrl (mod p), где l = ±1 и 1 rl. Тогда 2lq 2rl p - sin = l sin. Перемножим такие равенства для l = 1, 2,...,. При p p доказательстве леммы Гаусса было показано, что набор чисел r1,..., r(p-1)/p - совпадает с набором 1, 2,...,. Поэтому после сокращения получаем q 2lq 2l = 1... (p-1)/2 = sin sin.

p p p 1 l (p-1)/2l Воспользуемся тождеством из задачи 11.31 для 2k + 1 = q и = sin. В p результате получим q 2l 2m = (-4)(q-1)/2 sin2 - sin2 = p p q 1 l (p-1)/2 1 m (q-1)/ 2l 2m = (-4)(p-1)(q-1)/4 sin2 - sin2.

p q l,m Аналогично p 2m 2l = (-4)(p-1)(q-1)/4 sin2 - sin2.

q q p l,m p q Таким образом, чтобы получить из выражения для выражение для, q p p - 1 q - нужно поменять знак у каждого из · сомножителей. Следовательно, 2 p q = (-1)(p-1)(q-1)/4.

q p 382 Глава 31. Элементы теории чисел 3 p 31.43. Согласно квадратичному закону взаимности = p ±= (-1)(p-1)/2. Ясно также, что = ±1. Поэтому для p = 12k±1 получаем 3 ± = ±1, а для p = 12k ± 5 получаем = ±1.

p p -3 -1 3 31.44. Ясно, что = = (-1)(p-1)/2. Далее, p p p p (-1)(p-1)/2 = 1 для p = 12k+1 и p = 12k+5, (-1)(p-1)/2 = -1 для p = 12k-1 и p = 12k - 5. Воспользовавшись результатом задачи 31.43, получим требуемое.

31.45. Предположим, что существует лишь конечное число простых чисел вида 6k+1. Пусть N их произведение, а p простой делитель числа 4N2+3.

Число p нечётно и p = 3, так как N не делится на 3. Поскольку (2N)2 - -(mod p), то = 1. Согласно задаче 31.44 число p имеет вид 6k + 1. Но в p таком случае число N должно делиться на p. Итак, числа N и 4N2 +3 делятся на p. Следовательно, 3 делится на p, т.е. p = 3. Приходим к противоречию.

31.46. а) Ясно, что p -1 (mod 4). Кроме того, p 1 (mod 3). Действительно, n нечётно, поскольку число 22m - 1 делится 2m - 1, а потому не может быть простым при m > 1. А так как 22 1 (mod 3), то 2n - 1 (mod 3) для любого нечётного n. В результате получаем, что p 7 (mod 12).

Остаётся воспользоваться результатом задачи 31.43.

б) Ясно, что p 1 (mod 4). Кроме того, p -1 (mod 3). Действительно, n чётно, поскольку иначе число 2n + 1 делится 2 + 1 = 3. А так как 22 (mod 3), то 2n+1 -1 (mod 3) для любого чётного n. В результате получаем, что p 5 (mod 12). Остаётся воспользоваться результатом задачи 31.43.

31.47. Если n = 2m, то 2n - 1 делится на 22 - 1 = 3. Но число 3n - не делится на 3. Поэтому остаётся рассмотреть случай, когда n = 2m + 1.

Поскольку 24 22 (mod 12), то 22m 4 (mod 12), а значит, 2n - 1 (mod 12). Любое простое число p > 3 при делении на 12 даёт остаток ±1 или ±5. У числа 2n -1 должен быть простой делитель p > 3, дающий при делении на 12 остаток ±5.

Предположим, что 3n - 1 делится на 2n - 1. Тогда, в частности, 3n - делится на p. Следовательно, 32(m+1) = 3n+1 3 (mod p). Таким образом, = 1. Но это противоречит квадратичному закону взаимности (см. задаp чу 31.43).

p-1 k 31.48. Ясно, что g0 =. Половина чисел от 1 до p - 1 являются k=p квадратичными вычетами, а остальные невычетами.

31.49. Ясно, что p-1 p- k l kl g1 = k+l = k+l.

p p p k,l=1 k,l=Глава 31. Элементы теории чисел При фиксированном l отображение k kl является перестановкой остатков от деления на p, поэтому kl kl2 k k+l = kl+l = l(k+1) = p p p k,l k,l k,l -1 k = 0 + l(k+1) = p p l k =-1 l -1 k = (p - 1) + (-1), p p k =-поскольку при фиксированном k = -1 остатки от деления чисел l(k + 1) на p образуют набор 1,..., p - 1 и + 2 +... + p-1 = -1. Ясно также, что 2, -1 k + = g0 = 0.

k =-p p -31.50. Запишем тождество g1 = p для p = 5 и 7. Для p = 5 поp лучим g1 = ± 5, а для p = 7 получим g1 = ±i 7. Легко видеть, что это и есть требуемые тождества с точностью до знака. Знак в обоих случаях легко выясняется.

31.51. Для каждого натурального числа n p - 1 существует единственное натуральное число n p - 1, для которого n 1 (mod p). При этом n p - 1 = p - 1. Поэтому когда n пробегает числа от 1 до p - 2, n тоже пробегает числа от 1 до p - 2 (в другом порядке). Ясно также, что n2(1 + n) n2 + + n n(n + 1) (mod p), поэтому p-2 p-2 p- n(n + 1) n2(1 + n) 1 + n = = = g0 - = -1, p p p p n=1 n=1 n=поскольку g0 = 0 (задача 31.48).

n n + 31.52. а) Ясно, что = 1 в случаях RR и NN, а в случаях p p NR и RN это произведение равно -1. Следовательно, RR+NN -RN -NR = p-2 n(n + 1) =. Остаётся воспользоваться результатом задачи 31.51.

n=p б) Количество вычетов среди чисел 2, 3,..., p - 1 равно RR + NR, а количество невычетов равно RN + NN. Среди чисел 1, 2, 3,..., p - 1 вычетов и невычетов поровну. Кроме того, 1 вычет. Поэтому RN + NN = (p - 1) и RR + NR = (p - 1) - 1.

Количество вычетов среди чисел 1, 2,..., p 2 равно RR + а количе - RN, p - 1 -ство невычетов равно NR + NN. Кроме того, = =. Поэтому p p 1 RR + RN = (p - 2 - ) и NR + NN = (p - 2 + ).

2 384 Глава 31. Элементы теории чисел в) Сложим равенства RR + NN - RN - NR = 1, RR + RN = (p - 2 - ) и 1 NR+NN = (p-2+). В результате получим RR+NN = (p-3). Вычитая 2 1 из равенства RR+RN = (p-2-) равенство RN +NN = (p-1), получаем 2 1 p + 4 p - RR - NN = - ( + 1). Следовательно, RR = - и NN = +.

2 4 4 4 p p - После этого легко находим RN = - и NR = +.

4 4 4 Замечание. Равенства из задачи б) не являются независимыми: сумма равенств с равна RR + NN + RN + NR = p - 2; сумма равенств без та же самая.

31.53. а) Непосредственно следует из задачи 31.36.

б) Если целое число r удовлетворяет неравенствам 0 r < p, то r может принимать больше p различных значений (поскольку r может принимать значение 0). Таким образом, количество различных допустимых пар (r, s) больше p · p = p. Следовательно, для каких-то двух пар числа rx + s дают одинаковые остатки при делении на p.

в) Пусть r1x + s1 r2x + s2 (mod p), т.е. (r1 - r2)x (s2 - s1) (mod p).

Положим u = |r1 -r2| и v = |s1 -s2|. По построению числа u и v не могут быть одновременно равны нулю; кроме того, u, v < p. Так как ux ±v (mod p), то u2x2 v2 (mod p). Но x2 + 1 0 (mod p), поэтому 0 u2(x2 + 1) u2x2 + + u2 v2 + u2 (mod p). С другой стороны, u2 + v2 < ( p)2 + ( p)2 = 2p, поэтому u2 + v2 = p.

31.54. Согласно задаче 31.36 можно выбрать натуральное число q так, что q2 -1 (mod p). Рассмотрим число = q/p. Пусть C = p. Согласно задаче 17.12 можно выбрать натуральное число x < C = p и целое число x q y так, что |x - y| 1/C, т.е. - y. Положим r = xq - yp. Тогда p p |r| q x = - y, поэтому |r| p. Следовательно, 0 < x2 + r2 < 2p.

p p p С другой стороны, x2 + r2 x2 + x2q2 x2(1 + q2) 0 (mod p). Поэтому x2 + r2 = p.

31.55. а) Согласно задаче 31.36 можно выбрать натуральное число x так, что x2 -1 (mod p), т.е. x2 + 1 = mp. Таким образом, мы нашли требуемое решение, даже с дополнительным условием y = 1.

б) Пусть m0 наименьшее натуральное число, для которого имеет место равенство x2 + y2 = m0p. (1) К x и y можно добавлять кратные p, поэтому можно считать, что |x| < p/2 и |y| < p/2. Следовательно, x2 + y2 < p2/2, а значит, m0 < p/2.

Глава 31. Элементы теории чисел Пусть m0 > 1. Предположим, что m0 делит x. Тогда m0 не делит y, поx2 + y2 m0p p скольку иначе = = целое число, а это противоречит тому, m2 m2 m0 что 1 < m0 < p/2.

Выберем целые числа c и d так, чтобы числа x1 = x - cm0 и y1 = y - dmудовлетворяли неравенствам |x1| m0/2 и |y1| m0/2. Как только что было доказано, числа x1 и y1 не могут быть равны нулю одновременно. Таким m2 m2 0 образом, 0 < x2 + y1 2 = m0 и x2 + y1 x2 + y2 0 (mod m0).

1 4 Следовательно, x2 + y1 = m0m1, (2) где 0 < m1 m0/2. Перемножим равенства (1) и (2). В результате получим m2m1p = (x2 + y2)(x2 + y1) = (xx1 + yy1)2 + (xy1 - yx1)2.

0 При этом xx1 + yy1 = x(x - cm0) + y(y - dm0) = = x2 + y2 - m0(cx + dy) = = m0(p - cx - dy), xy1 - yx1 = x(y - dm0) - y(x - cm0) = = m0(cy - dx).

Таким образом, m2m1p = m2(X2 + Y ), где X = p - cx - dy и Y = cy - dx.

0 Сокращая на m2, получаем X2 + Y = m1p, причём 0 < m1 m0/2.

31.56. Предположим, что p = x2 + y2 = a2 + b2. Сравнение z2 -(mod p) имеет ровно два решения: z ±h (mod p). Поэтому x ±hy (mod p) и a ±hb (mod p). У чисел x и a можно поменять знаки, поэтому будем считать, что x hy (mod p) и a hb (mod p). Тогда xb ya (mod p).

Ясно, что p2 = (x2 + y2)(a2 + b2) = (xa + yb)2 + (xb - ya)2. (1) Но xb - ya 0 (mod p), поэтому (xa + yb)2 делится на p2. Итак, обе части равенства (1) можно сократить на p2. В результате получим представление числа 1 в виде суммы двух квадратов целых чисел. Такое представление единственно, поэтому либо xa + yb = 0, либо xb - ya = 0. Числа x и y взаимно простые, числа a и b тоже взаимно простые. Поэтому если xb = ya, то либо x = a и y = b, либо x = -a и y = -b. Если же xa = -yb, то либо x = b и y = -a, либо x = -b и y = a.

2 2 2 31.57. Пусть a = x2 + x2 + x2 + x2 и b = y1 + y2 + y3 + y4. Несложно 1 2 3 2 2 2 проверить, что ab = z1 + z2 + z3 + z4, где z1 = x1y1 + x2y2 + x3y3 + x4y4, z2 = x1y2 - x2y1 + x3y4 - x4y3, z3 = x1y3 - x3y1 + x4y2 - x2y4, z4 = x1y4 - x4y1 + x2y3 - x3y2.

386 Глава 31. Элементы теории чисел p - 31.58. Числа x2, где x целое число и 0 x, дают разные остатки при делении на p. Действительно, если x2 x2 (mod p), то x1 ± x2 1 (mod p). Но в рассматриваемой ситуации 0 < x1 + x2 < p. Аналогично числа p - -1 - y2, где 0 y, дают разные остатки при делении на p. Количество чисел в обеих группах равно p + 1, поэтому какие-то два числа дают одинаковые остатки при делении на p. Эти числа должны быть из разных групп. Таким образом, x2 -1 - y2 (mod p), т.е. 1 + x2 + y2 = mp, причём 2 2 p - 1 p p x2, y2 <. Следовательно, 1 + x2 + y2 < 1 + 2 < p2, а 2 2 значит, 0 < m < p.

31.59. а) Непосредственно следует из задачи 31.58: можно положить x1 = = 1, x2 = x, x3 = y и x4 = 0.

б) Предположим, что число x2 + x2 + x2 + x2 чётно. Тогда количество 1 2 3 нечётных чисел среди x1, x2, x3 и x4 чётно. Поэтому можно считать, что числа x1 и x2 одной чётности и числа x3 и x4 тоже одной чётности. Тогда тождество 2 2 2 2 m x1 - x2 x1 + x2 x3 - x4 x3 + x+ + + = p 2 2 2 2 показывает, что чётное число m можно заменить на меньшее число m/2.

в) Предположим, что m0 наименьшее из рассматриваемых чисел m, причём m0 = 1. Согласно задаче б) число m0 нечётно. Поэтому каждое число xi можно представить в виде xi = m0bi + yi, где |yi| < m0/2. Действительно, если ri остаток от деления xi на m0, то одно из чисел ri или m0 -ri меньше m0.

Числа x1, x2, x3 и x4 не могут все делиться на m0, поскольку иначе m0p = = x2 + x2 + x2 + x2 делится на m0, а значит, p делится на m0. Но 1 < m0 < p.

1 2 3 Следовательно, хотя бы одно из чисел y1, y2, y3 и y4 отлично от нуля. Таким образом, 2 2 2 0 < y1 + y2 + y3 + y4 < 4 m0 = m2. (1) Кроме того, yi xi (mod m0), поэтому 2 2 2 y1 + y2 + y3 + y4 x2 + x2 + x2 + x2 = m0p 0 (mod m0). (2) 1 2 3 2 2 2 Из (1) и (2) получаем, что y1 + y2 + y3 + y4 = m0m1, где 0 < m1 < m0.

2 2 2 Умножим число x2 + x2 + x2 + x2 = m0p на y1 + y2 + y3 + y4 = m0m1 и 1 2 3 воспользуемся тождеством из решения задачи 31.57. В результате получим 2 2 2 равенство вида z1 + z2 + z3 + z4 = m2m1p. Несложно проверить, что каждое из чисел z1, z2, z3, z4 делится на m0. Действительно, z1 = xi(xi - bim0) x2 m0p 0 (mod m0), i z2 = x1(x2 - b2m0) - x2(x1 - b1m0) + x3(x4 - b4m0) - x4(x3 - b3m0) = = m0(-x1b2 + x2b1 - x3b4 + x4b3) 0 (mod m0).

Для z3 и z4 доказательство аналогично.

Глава 31. Элементы теории чисел Положим ti = zi/m0. Тогда t2 + t2 + t2 + t2 = m1p, где 0 < m1 < m0. Это 1 2 3 противоречит предположению о том, что число m0 наименьшее.

31.60. Согласно задаче 31.59 любое нечётное простое число можно представить в виде суммы четырёх квадратов целых чисел. Число 2 можно представить так: 2 = 12 + 12 + 02 + 02. Остаётся воспользоваться результатом задачи 31.57.

31.61. Пусть p - 1 = qd + r, где 0 r < d. Тогда 1 xp-1 xqd+r xr (mod p). Но d это наименьшее натуральное число, для которого xd (mod p). Следовательно, r = 0.

31.62. Решение аналогично решению задачи 31.61.

Pages:     | 1 |   ...   | 44 | 45 || 47 | 48 |   ...   | 65 |



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

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