Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/03/61.pdf Дата изменения: Fri Dec 23 19:25:52 2005 Дата индексирования: Tue Oct 2 00:15:47 2012 Кодировка: Windows-1251

ОТВЕТЫ,

УКАЗАНИЯ,

РЕШЕНИЯ

61

10 + 3 1 3 + 3 = 84 0 mod 7 . в) Указание. = 10 Пусть p простой делитель числа ab + c. Существует бескоn нечно много таких натуральных n, что b b mod p . 13. Порядок числа a является делителем чисел r и s и потому является делителем числа НОД(r,s). 14. При k, кратных 18. 100 . 16. Например, k = 10

ej
6

k

4

4

b

g

b

g

+ a mod 2 . Указание. По26. а) Ответ: x + a или 2 скольку x + a x - a = 2a, числа x a и x + a не могут оба делиться на 4. Значит, либо одно из них делится на 2 m , либо одно делится на 2 m -1 , а другое четно. 27. Указание. Докажите по индукции сравнения

b

gb
e

g

m -1

e

m

j

18. Указание. 2 + 6 = 100 . Докажите, что если число n обладает нужным свойством, то число n + 100 тоже обладает им. 19. При p = 2 годится любое четное n. Пусть p > 2 и n = n =(p 1)m. Тогда 2 1 и n - m mod p , так что в качестве m можно взять любое натуральное число вида m = ps 1, где s = 1, 2, 3, ... 21. а) 20; б) 20.

6

2

e

j

, где p нечетное простое, m 2. 28. г) Всякое натуральное число вида 6m 1 имеет хотя бы 2 один простой делитель вида p = 6k 1. Пусть a + a + 1
mod p

b1 + pg

5

2

m -3

1+2
p m-2

m -1

mod 2
m -1

m

1 + p

e

j

, где m 3 , и
m

j

b

g

кратно p. Тогда a 3 1 = a - 1 a + a + 1 тоже кратно p. Если a 1 mod p , то a + a + 1 1 + 1 + 1 = 3, что невозможно, ибо p 3 . Значит, порядок числа a по модулю p равен 3, откуда p 1 кратно 3. Но p 1 = 6k 2 не кратно 3. 29. Указание. a
12

b

g

b

2

ge

2

2

j

22. а) Указание. Поскольку 2000 делится и на 2 на 5
4

лю 5 . Следовательно, 3 = ...6667. б) Поскольку 5
500 4 4 3

ej
4

= 4 5 , имеем: 3

3

2000

1 и по модулю 2 , и по моду-

4

ej
4

= 8, и
1999

-1 = a -1 a +1 a - a +1 .
15

e

6

2000

1 mod 10000 . Ответ: 3
2000

b

g

=

30. в) Указание. a

оканчивается теми же четырьмя цифрами, что и число 2 313 + 625 7 = 4688. в) Указание. 10000 = 16 625. Число 2
2000 3

e j = 5 b5 - 1g = 500, то 2 = = e 2 j 1 -624 e mod 5 j , так что 2 - 624 2 = =312 313 e mod 5 j . Осталось подобрать такое целое x, что 313 + 625x делится на 16. Это легко: 313 = 320 7 -7 и 625 = 624 + 1 1 b mod 16 g , так что годится x = 7. Значит,
4 1999 4 1999

Ч a -a +a 31. Указания. 2 +1 - a mod 4 a mod p . 33. Указание.

e

-1 = a -1 a + a +1 a + a + a + a +1 Ч
3

b

je j

2

8

7

5

b

b

g

- a + a - a +1 . а) В силу предыдущего упражнения a + 3 2 p . б) Докажите, что a - a + a - 1

4

ge

2

je

4

2

je

4

j

3

2

j

g

Число ac + 1 кратно p. 34. Указание. Если p простой общий делитель чисел n и
n
n +1

bg

2

n

Существует такое целое c, что bc 1 mod p .

b

g

кратно 16. В силу

n +1 2 > n. a + 1 , то p n и p = 2 k + 1 > 2 n 35. а) Пусть n четно и a + 1 делится на n + 1. Записав n = m = 2 k , где k нечетное, имеем: любой простой делитель чисm

теоремы Эйлера, остаток от деления 3

2000

скольку 625 = 500, имеем: 2 2 mod 625 . Осталось подобрать такое целое x, что 2 + 625x делится на 16. Ответ: 8752. 23. Достаточно разобрать случай x y . Поскольку 1998 = 3 = 2 3 37 , достаточно доказать отсутствие решений в натуральных взаимно простых числах x, y, где x y , и целых 7 7 неотрицательных числах a, b, c уравнения x + y = = 2 3 37 . Обозначим N = 2 3 37 и f = N . Поскольку f не делится на 7, существует такое натуральное число t, что 7t 1 mod f . Возводя сравнение x - y ем: x
7t a b c a b c

bg

2000 3

b

на 500 равен 1; по-

g

+ 1 сравним с 1 по модулю 2 . ла a + 1 = a Поскольку произведение чисел, сравнимых с 1 по модулю m +1 2 , тоже сравнимо с 1 по этому модулю и поскольку n + 1=
m

n

ej
k

2

m +1

= 2 k + 1 1 mod 2 , получаем противоречие. / Итак, n нечетно. Теперь очевидно, что a тоже нечетно. б) Указание. Рассмотрите n = a . 36. а) Следует из предыдущего упражнения. б) Убедитесь, n n что если 2 + 2 кратно n и если 2 + 1 кратно n 1 (это верно, например, для n = 2), то 2
2
n 2 +2 n 2 +2 a m

e

m +1

j

bg

+ 2 кратно 2 + 2 и
2

n

b

7

g

+ 1 кратно 2 + 1 .
2 4 4

n

7

-y

Поэтому x x

ej
7

t

. Очевидно, число t нечетно (ибо f четно).

b

mod N в t-ю степень, получа7t

g

37. Пусть 15a + 16b = r и 16a 15b = s , где r, s натуральные числа. Тогда r + s = 15 a + 16b = 15 + 16

7t

-y
7

делится на N = x + y , что невозможно из-за неравенства 7 7 x+y < x +y . s +1 s 24. Пусть k 1 делится на 2 и не делится на 2 . Предположим, что при всех достаточно больших натуральных l число p = 2 + k простое. Очевидно, если 2 > s, то p 1 = 2 В силу теоремы Эйлера, 2 b g 1 mod h . Поэтому s +bhg s s 2 mod 2 h . Следовательно, при l s имеем 2
h l 2 l l 2

ej
7 7

t

= -y

- y mod N , так что x + y

b

g

+

+k 1 = 2 h , где h нечетно.

s

. 2 2 В силу малой теоремы Ферма,
2
l+ h 2

l+ h

bg

l

e j mod p - 1g b
l+ h 2

b

g

bg

+ k со+ k > 2 + k = p , то число 2 Поскольку 2 ставное. Задача решена. 25. а) n = 1, p m или 2 p m , где p простое, m натуральное.

bg

+k 2
l 2

l 2

+ k 0 mod p .

b

g

l+ h 2

bg

не имеет вида 8k + 1, а r + s 4 делится на 13, то r s 0 mod 13 . Аналогично, r s 0 mod 37 . 2 2 Ответ: 13 37 (при a = 13 37 31 , b = 13 37 ). 39. Примените утверждение предыдущего упражнения: а) при a = 8; б) при a = 512. 40. Достаточно разобрать случай a b . Числа a и b нечетны. Обозначим буквой n их наименьшее общее кратное. Тогда n a 2 + 1 кратно числу 2 + 1 , которое кратно числу b. Аналоb n n гично, 2 + 1 кратно 2 + 1, которое кратно a. Значит, 2 + 1 кратно как a, так и b, а следовательно, и их наименьшему общему кратному n. Поскольку n > 3, то, в силу пункта а) предыдущего упражнения, n кратно 9. Предположим для определенности, что a не кратно 3. Тогда легко проверить, что 2a + 1 не делится на 9. Это противоречит тому, что b делится на 9. n 2 41. Указание. Пусть n > 3 и 2 + 1 кратно n . Представим n a в виде n = 3 m , где m не кратно 3. Тогда a > 1. Индукцией

e

2

2

je

a +b

2

2

j

= 13 37 a + b . Поскольку число 13
4

e

b

2

2

j

g + b16
2

a - 15b

g

2

=

b

g

b

g