WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 43 | 44 || 46 | 47 |   ...   | 65 |

1 2 3 n 31.10. П е р в о е р е ш е н и е. Рассмотрим дроби,,,..., ; их колиn n n n чество равно n. Заменим каждую из этих дробей на соответствующую несократимую дробь. При этом получатся дроби, знаменателями которых являются делители числа n, причём количество дробей со знаменателем d равно (d).

В т о р о е р е ш е н и е. Запишем разложение числа n на простые множители: n = p1p2... pk. Любой делитель d числа n имеет вид d = p1p2... pk, 1 2 k 1 2 k где 0 i i, i = 1,..., k. Поэтому в силу свойства мультипликативности функции Эйлера (задача 31.7 б) (d) = 1 + (p1) +... + (p1)... 1 + (pk) +... + (pk).

1 k Действительно, в правой части после раскрытия скобок мы получаем сумму всех слагаемых вида (p1)... (pk) = (p1... pk). Остаётся заметить, что 1 k 1 k 1 + (p) +... + (p) = 1 + (p - 1) + (p2 - p) +... + (p - p-1) = p.

31.11. а) О т в е т: 7. Числа 171 и 52 взаимно простые, поэтому 171(52) 1 (mod 52). Далее, (52) = (4)(13) = 24. Поэтому 1712147 1524·89+11 1511 7 (mod 52).

б) О т в е т: 54. Числа 126 и 138 не взаимно простые: НОД(126, 138) = 6.

Мы воспользуемся тем, что если a b (mod 23), то 6a 6b (mod 138). Пусть 374 Глава 31. Элементы теории чисел a = 21 · 1261019. Тогда a 21 · 1122·46+7 -2 · 117 9 (mod 23). Поэтому 1261020 = 6a 54 (mod 138).

31.12. Согласно теореме Эйлера a(m) 1 (mod m). Поделим (m) на k с остатком: (m) = kq + r, где 0 r < k. Тогда 1 a(m) (ak)qar ar (mod m). Следовательно, r = 0, поскольку иначе мы получили бы противоречие с минимальностью числа k.

31.13. Числа a и an - 1 взаимно простые. Поэтому согласно теореме Эйn лера a(a -1) 1 (mod an - 1). Из этого следует, что число (an - 1) делится на n (см. задачу 31.20).

i-31.14. Согласно теореме Эйлера xpi (pi-1) 1 (mod pi). Возведём обе i L(n) части этого равенства в степень (это число целое, поскольку i-pi (pi - 1) L(n) делится на pi-1(pi - 1)). В результате получим xL(n) 1 (mod pi).

i i Следовательно, число xL(n) - 1 делится на p1,..., pk, поэтому оно делится 1 k на n.

31.15. а) Предположим, что число p простое и p > 2 (для p = 2 требуемое утверждение очевидно). Пусть a одно из чисел 1, 2, 3,..., p - 1. Для него существует единственное число, 1 p - 1, для которого a 1 (mod p) (см. решение задачи 4.63). Если a =, то a2 - 1 = (a - 1)(a + 1) делится на p, поэтому a = 1 или p - 1. Таким образом, числа 2, 3,..., p - 2 разбиваются на пары, произведения которых дают остаток 1 при делении на p. Значит, (p - 1)! p - 1 -1 (mod p).

Предположим теперь, что p = qr, где 1 < r, q < p. Тогда (p - 1)! делится на q, поэтому (p - 1)! -1 (mod p).

б) Предположим, что p = qr, где 1 < r < q < p. Тогда (p - 1)! делится на qr = p. Остаётся рассмотреть случай, когда p = q2, где q простое число.

Если q = 2, то q2 = 4 и (3!)2 = 36 делится на 4. Если же q > 2, то (p - 1)! делится на q и на 2q, поэтому даже само число (p-1)!, а не только его квадрат, делится на q2 = p.

31.16. Если число n простое, то согласно теореме Вильсона (задача 31.15 а) a(n) = 1 и b(n) = 0, поэтому f(n) = n. Если же число n со ставное, то, как следует из решения задачи 31.15 б), (n - 1)! 0 (mod n) и 2(n - 1)! 0 (mod n). Поэтому a(n) = 0 и b(n) = 1, значит, f(n) = 2.

31.17. Число a - b делится на n1, n2,..., nk, поэтому оно делится и на наименьшее общее кратное этих чисел.

31.18. Применим индукцию по r. Предположим, что xn = a + mpr. Будем r искать целое число t так, чтобы для числа xr+1 = xr + tpr выполнялось сравнение xn a (mod pr+1). Ясно, что r+n(n - 1) xn = (xr + tpr)n = xn + nxn-1tpr + xn-2t2p2r +...

r+1 r r r = a + mpr + nxn-1tpr +...

r Глава 31. Элементы теории чисел Здесь многоточием обозначены члены, делящиеся на pr+1. Таким образом, нужно выбрать t так, чтобы число mpr + nxn-1tpr делилось на pr+1, т.е.

r число m + nxn-1t делилось на p. По условию числа n и a не делятся на p.

r Поэтому число nxn-1 тоже не делится на p. В таком случае для любого числа r m можно выбрать число t так, что nxn-1t -m (mod p).

r 31.19. По условию a = b + mpn, где m целое число. Поэтому p(p - 1) ap = bp + pbp-1mpn + bp-2(mpn)2 +...

p(p - 1) Все слагаемые pbp-1mpn, bp-2(mpn)2,... делятся на pn+1.

31.20. Запишем k в виде k = pn + r, где 0 r < n. Ясно, что an 1 (mod an - 1), поэтому ak ar (mod an - 1). Но если r > 0, то a ar an-1 < an - 1. Поэтому ar 1 (mod an - 1) тогда и только тогда, когда r = 0, т.е. число k делится на n.

31.21. Применим индукцию по n. При n = 1 утверждение верно. Действительно, если не все коэффициенты многочлена f(x) делятся на p, то cf(x) xm + a1xm-1 +... + am (mod p) для некоторого целого числа c;

здесь m < p. Поэтому согласно теореме Лагранжа (задача 31.33) сравнение cf(x) 0 (mod p) имеет место не более чем для m различных по модулю p значений x. Поскольку m < p, найдётся x, для которого f(x) 0 (mod p).

Предположим, что требуемое утверждение доказано для некоторого n.

Рассмотрим тождественное сравнение f(x1,..., xn, xn+1) 0 (mod p), у которого степень по каждой переменной меньше p. Запишем f(x1,..., xn, xn+1) в виде gm(x1,..., xn)xm + gm-1(x1,..., xn)xm-1 +... + g0(x1,..., xn).

n+1 n+Фиксируем x1,..., xn; пусть am = gm(x1,..., xn),..., a0 = g0(x1,..., xn).

Сравнение amxm +...+a0 0 (mod p) выполняется для всех целых xn+1, поn+этому a0... am 0 (mod p). Таким образом, gi(x1,..., xn) 0 (mod p) для всех целых x1,..., xn. Поэтому по предположению индукции все коэффициенты многочлена gi(x1,..., xn) делятся на p.

31.22. Согласно малой теореме Ферма xp xi (mod p), поэтому i xm xr (mod p). Значит, после указанных замен мы получим многочлен i i g(x1,..., xn), степень которого по каждой переменной строго меньше p, причём g(x1,..., xn) 0 (mod p) для все целых x1,..., xn. Согласно задаче 31.все коэффициенты многочлена g(x1,..., xn) делятся на p.

31.23. Предположим, что сравнение f(x1,..., xn) 0 (mod p) имеет только решение (0,..., 0). Тогда сравнение p-1 - f(x1,..., xn) (1 - xp-1)... (1 - xp-1) (mod p) (1) n выполняется тождественно. При (x1,..., xn) = (0,..., 0) это очевидно, а при (x1,..., xn) = (0,..., 0) это следует из малой теоремы Ферма.

376 Глава 31. Элементы теории чисел Применим к обеим частям сравнения (1) замены, описанные в условии задачи 31.22. С одной стороны, согласно этой задаче в результате мы должны получить тождественное сравнение. С другой стороны, в правой части вообще никаких замен не делается, поэтому в правой части после замен стоит многочлен, моном высшей степени которого равен ±xp-1... xp-1. В левой же части n первоначально стоит многочлен степени меньше n(p - 1); после указанных замен его степень может только уменьшиться. Получено противоречие.

31.24. Это утверждение очевидным образом следует из теоремы Шевалле (задача 31.23), поскольку степень рассматриваемого многочлена строго меньше числа его переменных.

31.25. а) Делителями числа pa являются числа 1, p, p2,..., pa.

б) Пусть d и d делители чисел m и n. Тогда dd делитель числа mn. Для взаимно простых чисел m и n верно и обратное: любой делитель числа mn однозначно представляется в виде произведения делителей чисел m и n. Поэтому если k(m) = ak и k(n) = bk, то k(mn) = akbk = i j i j = ( ak)( bk) = k(m)k(n).

i j 31.26. а) 2p-1 и (2p - 1) взаимно простые, поэтому согласно зада Числа че 31.25 б) 2p-1(2p - 1) = (2p-1)(2p - 1). Далее, согласно задаче 31.25 а) (2p-1) = 1 + 2 + 4 +... + 2p-1 = 2p - 1 и (2p - 1) = 1 + 2p - 1 = 2p.

б) Пусть n = 2p-1m, где m нечётно, чётное совершенное число. Тогда 2pm = 2n = (n) = (2p-1)(m) = (2p - 1)(m). Поэтому m делится на 2p - 1.

Пусть m = (2p - 1)m. Тогда 2p(2p - 1)m = 2pm = (n) = (2p-1)(m) = = (2p - 1)(m), поэтому (m) = 2pm. Из равенства m = (2p - 1)m следует, что m + m = 2pm = (m). С другой стороны, оба числа m и m являются делителями числа m. Поэтому равенство m + m = (m) может выполняться лишь в том случае, когда число m простое и m = 1.

31.27. Пусть n = pa1pa2, где p1 и p2 простые числа, причём p1 3 и 1 p2 5. Тогда из неравенства pa1+1 - 1 pa2+1 - 1 pa1+1 pa2+1 p1 p1 2 1 (n) = · < · = n · p1 - 1 p2 - 1 p1 - 1 p2 - 1 p1 - 1 p2 - следует, что (n) p1 p2 3 5 < · · = < 2.

n p1 - 1 p2 - 1 2 4 31.28. Число (n)/n является суммой всех чисел вида d/n, где d делитель числа n. Но d/n = d, где d некоторый делитель числа n, причём когда d пробегает все делители числа n, d тоже пробегает все делители числа n. Значит, (n)/n = 1/d, где сумма берётся по всем делителям числа n.

d Положим n = N!. Тогда (n) 1 1 1 1 + + + +... +, n 2 3 4 N поскольку числа 1, 2, 3,..., N являются делителями числа n. Остаётся заметить, что гармонический ряд расходится (задача 30.6).

Глава 31. Элементы теории чисел 31.29. а) О т в е т: 5 и 8.

б) Пусть n = pa1... pak и p1 > p2 >... > pk. Тогда n(n) = 1 k k = p2ai-1(pi - 1) и наибольшее простое число, на которое делится i=1 i n(n) равно p1. При этом максимальная степень числа p1, на которую делится n(n), равна 2a1 - 1. Таким образом, если известно число n(n), то n(n) известны числа p1 и a1. Пусть n = pa1n2. Тогда n2(n2) =, p2a1-1(p1 - 1) поэтому известны числа p2 и a2 и т.д.

в) О т в е т: 12 и 14.

2n + 2 2n 31.30. Ясно, что - = 0, если числа 2n+1 и 2n+2 не делятся k k на k. В противном случае эта разность равна 1. Следовательно, n+2 n 2n + 2 2n - = 0(2n + 1) + 0(2n + 2) + 1.

k k k=1 k= 2n n 2n Поэтому если f(n) = 0(k) -, то f(n + 1) - f(n) = 1. Ясно k=1 k=k также, что f(1) = 1.

31.31. Прежде всего проверим, что при всех n > 1 выполняется соотно шение µ(d) = 0. Пусть n = p1 ·... · pk. Тогда 1 k d|n k k µ(d) = µ(d) = 1 - + +... + (-1)k = (1 - 1)k = 0.

1 d|n d|p1...pk Ясно, что f(d1) µ(b).

F (a)µ(b) = f(d1)µ(b) = ab=n d1d2b=n d1|n d2b=n/dПусть n/d1 = m. Тогда 1 при n = d1;

µ(b) = µ(b) = 0 при n = d1.

d2b=m b|m Поэтому f(d1) µ(b) = f(n).

d1|n d2b=n/d31.32. Непосредственно сводится к задаче 31.31 с помощью логарифмирования.

31.33. Применим индукцию по n. При n = 1 утверждение очевидно. Пусть числа f(x1) и f(x) делятся на p (x целое число). Тогда число f(x)- f(x1) = = xn-xn+a1(xn-1-xn-1)+an-1(x-x1) = (x-x1)g(x) делится на p. При этом g(x) = xn-1 + b1xn-2 +... + bn-1 многочлен с целыми коэффициентами, зависящими только от a1,..., an и x. Если 0 x p - 1 и x = x1, то x - x 378 Глава 31. Элементы теории чисел не делится на p. Поэтому на p должно делиться число g(x), и мы можем воспользоваться предположением индукции.

31.34. Сопоставим каждому целому числу x, где 1 x p - 1, остаток от деления на p числа x2. Числам x и p - x сопоставляется одно и то же число, причём x = p - x. Кроме того, согласно теореме Лагранжа (задача 31.33) сравнение x2 c (mod p) не может иметь больше двух решений. Поэтому образ рассматриваемого отображения состоит из (p - 1)/2 элементов. А этот образ как раз и состоит из квадратичных вычетов.

31.35. Если a b2 (mod p), то согласно малой теореме Ферма (задача 31.1) a(p-1)/2 bp-1 1 (mod p). Поэтому любой квадратичный вычет является решением уравнения x(p-1)/2 1 (mod p). Согласно теореме Лагранжа (задача 31.33) количество решений этого сравнения не превосходит (p-1)/2, а согласно задаче 31.34 количество квадратичных вычетов равно (p-1)/2. Поэтому квадратичные вычеты это в точности решения сравнения x(p-1)/2 1 (mod p).

Если a квадратичный невычет, то a(p-1)/2 -1 (mod p). Действительно, сравнение x2 1 (mod p) имеет только два решения: x ±1 (mod p), а мы знаем, что (a(p-1)/2)2 = ap-1 1 (mod p).

31.36. Воспользуемся критерием Эйлера (задача 31.35). Если p = 4k + 1, то (-1)(p-1)/2 = (-1)2k = 1, а если p = 4k + 3, то (-1)(p-1)/2 = (-1)2k+1 = -1.

31.37. Предположим, что уравнение x2 - dy2 = -1 не имеет решений в целых числах. Пусть (, ) фундаментальное решение уравнения Пелля x2 - dy2 = 1. Число d тоже имеет вид 4k + 1, поэтому 2 (2 + 1) (mod 4).

Квадрат нечётного числа при делении на 4 даёт остаток 1, поэтому нечётно, ( - 1)( + 1) а чётно. Равенство = показывает, что 2/4 (квадрат целого 4d числа) можно представить в виде произведения двух квадратов целых чисел:

( - 1) ( + 1) u2 = и v2 =, где d1 и d2 делители числа d. Натуральные 2d1 2dчисла u и v взаимно простые, потому что НОД( - 1, + 1) = 2. Кроме того, u = 0, поскольку = 1. Далее, 1 d2v2 - d1u2 = ( + 1) - ( - 1) = 1.

2 Предположим, что d1 = 1 и d2 = 1. По условию r = 2 или нечётно, поэтому d1 или d2 произведение нечётного числа простых чисел.

Случай 1. d1 произведение нечётного числа простых чисел.

Пусть p произвольный простой делитель числа d2. Тогда d1 pi1 pi2k+=... = (-1)2k+1 = -1.

p p p Но это противоречит тому, что d1u2 -1 (mod p), поскольку -1 является квадратичным вычетом по модулю p.

Глава 31. Элементы теории чисел Случай 2. d2 произведение нечётного числа простых чисел.

dСнова для произвольного простого делителя p числа d1 получаем = p = -1. Но это противоречит тому, что d2v2 1 (mod p).

Полученные противоречия показывают, что либо d1 = 1 и d2 = d, либо d1 = d и d2 = 1.

Случай 1. d1 = 1 и d2 = d, т.е. dv2 - u2 = 1.

Это противоречит предположению о том, что уравнение x2 - dy2 = -1 не имеет решений.

Случай 2. d1 = d и d2 = 1, т.е. v2 - du2 = 1.

Таким образом, (v, u) решение уравнения Пелля x2 - dy2 = 1. С другой 2 - 1 стороны, u2v2 = =, поэтому uv =, а значит, u <. Но это 4d 4 противоречит тому, что было выбрано фундаментальное решение.

31.38. Прежде всего заметим, что если l и k различные натуральные p - числа от 1 до, то rl = rk. Действительно, если rl = rk, то (l±k)q делится на p, поэтому l ± k делится на p. Но |l ± k| p - 1.

Таким образом, набор чисел r1, r2,..., r(p-1)/2 совпадает с набором p - 1, 2,...,. Поэтому, перемножив сравнения q ±r1 (mod p),..., p - q ±r(p-1)/2 (mod p), получим p-p - 1 p - !q (-1)µr1... r(p-1)/2 = (-1)µ ! (mod p).

2 p-1 p-q 2 Следовательно, q (-1)µ (mod p). Но q (mod p) (задаp ча 31.35).

31.39. Рассмотрим многочлен A(x1,..., xp) = (xi - xj). Под дей1 i

1 i

Pages:     | 1 |   ...   | 43 | 44 || 46 | 47 |   ...   | 65 |



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

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