Deza_Kotova_Sbornik_zadach_po_teorii_chisel

= 2 · 2а-1 , верное при всех таких а и {3.

Если а #О, /3 #О, то уравнение принимает вид 2а.2.3.в-1 = 2.3.В.2a-l,

что вновь ведет к противоречию.

Таким образом, множеству решений уравнения ~(2х) = ~(3х) при­

надлежат все натуральные числа вида 2ау, где а Е N, а натуральное

6.Решите уравнение ~(х) = 2.

Решение. Очевидно, что х # 1. В этом случае х обладает каноническим

имеется не более т нечетных простых множителей. Другими словами, k ~ m+ 1, причем если k = т+ 1, то Р1=2.

В нашем случает=~. то есть k ~ 2, причем если k = 2, то р1 = 2. Пусть k = 1, то есть х = ра.

Если р = 2, то ~(х) = ~(2а) = 2а-1 , и наше уравнение принимает вид 2a-l = 2,

Если р # 2, то ~(х) = ~(ра) = ра-1 (р- 1), и наше уравнение при­

нимает вид pa-I (р - 1) = 2, откуда следует, что р - 1 = 2 и pa-I = 1.

Таким образом, р = 3, а= 1, их= 3.

Пусть k = 2, то есть х = 2ар.б.

Тогда ~(х) = ~(2ар.б) = 2а-1р.б-1 (р- l), и наше уравнение принимает

6. Сколько существует правильных несократимых дробей со знаменате­

лем, делящим 2002?

7.Сколькими нулями оканчивается число:

а) rp(528)! в 12-й системе счисления; б) rp(506)! в 48-й системе счисления; в) rp(400)! в 48-й системе счисления;

r)rp(396)! в 48-й системе счисления?

8.Найдите число натуральных чисел, не превосходящих 1000 и взаимно

простых с 77.

9.Найдите число натуральных чисел, не превосходящих 875 и взаимно простых с 175.

10.Найдите число натуральных чисел, не превосходящих 230 - 1 и вза­ имно простых с 210 - 1.

11.Найдите число натуральных чисел, не превосходящих 8! и взаимно простых с 6!.

12.Найдите число натуральных чисел n, не превосходящих 1665 и удо­

влетворяющих условию (1665, n) = 15.

13.Решите уравнение:

14. Найдите все четные натуральные n :::;; 50, для которых уравнение rp(x) = n не имеет решений.

15. Решите уравнение:

19.Решите уравнение ip(x) = (р- l)x/p, если р - простое число.

20.Найдите натуральное число п, если п = 3а · 5/3, и ip(n) = 600.

21.Найдите натуральное число п, если ip(7n) = 705 894.

22.Найдите натуральное число п, если ip(3n) = 162.

23.При каких натуральнь1х х имеет место равенство:

а) ip(6x - 3) = ip(2x - l);

б) ip(3x + 1) = ip(6x + 2); в) ip(3x - 1) = ip(9x - 3).

24. При каких натуральных п имеет место соотношение 2Jip(n)?

00ip(pk)

25.Вычислите 2: -k-, где s Е JR., s > 1.

k=O р 8

26. Докажите:

к) р, 2р + l ЕР => ip(4p + 2) = ip(4p) + 2.

27. Докажите, что J{x Е N: х ~ km, (х, m) = l}I = kт Пр\т(l - 1/р),

где. k,m Е N.

28.Что больше: ip(m2) или ip2(m)?

29.Докажите:

i-~ 1. Функция Мебиуса

Рассмотрим функцию Мебиуса µ(п), определенную для всех натураль­

ных п и принимающую значения из множества {-1, О, 1} в зависимости

от разложения п на простые множители: µ(п) = 1, если п - бесквад-

64 Глава 1. Задачи по курсу теории чисел

ратное число с четным числом простых делителей; µ(n) = -1, если n -

Например, µ( 6) = 1, поскольку 6 = 2 · 3 - бесквадратное число, имеющее два простых делителя; µ(70) = -1, поскольку 70 = 2 · 5 · 7 - бесквадратное число, имеющее три простых делителя; µ(50) = О, поскольку 50 = 2 · 52 делится на квадрат простого числа 5, и, следовательно, не является

бесквадратным.

4.Е µ(d)т(n/d) = 1. dJn

5.Е µ(d)n/d = <p(n).

dJn

6.l:µ(d)u(n/d) = n. dJn

Так, первое свойство можно доказать непосредственной проверкой. Для доказательства второго свойства прежде всего убедимся в том, что

Доказательство формулы обращения Мебиуса основано, с одной стороны,

на цепочке равенств

Lµ(d)F(n/d)= Lµ(d) Lf(c)= Lµ(d)/(c)= Lf(c) Lµ(d)=f(n).

Более детальные рассуждения можно найти, например, в [3].

66 Глава 1. Задачи по курсу теории чисел

+О· 2 + (-1) · 3 + (-1)2 • 2 +О· 1 = 6- 4 - 3 + 2 = 1. Доказать тож­

доказательство можно получить и непосредственно: 2:: µ(d)т(n/d) =

68 Глава 1. Задачи по курсу теории чисел

§ 12. Отношение сравнимости

Два целых числа а и Ь называются сравнимыми по модулю n, n Е N, если а и Ь имеют одинаковые остатки при делении на n, или, что то же,

5 =/:- -4(mod 7), так как 5 = 7 ·0+5, но -4 = 7 · (-1) +3; другими словами,

5 - (-4) = 9, и 7f 9.

Свойства отношения сравнимости

1. Отношение сравнимости =является отношением эквивалентности,

то есть:

•а= a(mod n) для любого целого а;

• если а= Ь(mod n), то Ь =a(mod n);

•если а= Ь(mod n) и Ь =c(mod n), то а= c(mod n).

2.Если а =Ь(mod n), то /(а) =/(Ь)(mod n) для любого многочлена

/(х) с целыми коэффициентами.

а= Ь(mod n) =kЬ(mod kn), k Е N.3. ~ гдеka

4. а= Ь(mod n) ~ ka =kЬ(mod n), где k Е Z, (k, n) = 1.

а= Ь (modn1)

а= Ь (modn2)

5.~ а= Ь(mod М), где М = [n1, n2, ... , nk].

Так, доказательство первого свойства следует из определения: а = a(mod n), поскольку а - а = О, и nlO; если а =Ь(mod n), то nl(a - Ь), и, следовательно, nl(Ь - а), то есть Ь =a(mod n); если а= Ь(mod n) и Ь = c(modn), то nl(a-Ь), nl(Ь-c) и, следовательно, nl(а-Ь)+(Ь-с), то есть nl(a-c), и а= c(modn). Таким образом, отношение сравнимости обладает

свойствами рефлекстивности, симметричности и транзитивности, то есть