Книги по разным темам Pages:     | 1 |   ...   | 3 | 4 | 5 | 6 | 7 |   ...   | 65 |

4.3. Пусть a1,..., a2n+1 целые числа, b1,..., b2n+1 те же самые числа, но записанные в другом порядке. Докажите, что хотя бы одно из чисел ak - bk, k = 1, 2,..., 2n + 1, чётно.

4.4. Пусть a, b, c целые числа, причём a = 0. Докажите, что если квадратное уравнение ax2 + bx + c = 0 имеет рациональный корень, то по крайней мере одно из чисел a, b, c чётно.

4.5. Докажите, что многочлен с целыми коэффициентами a0xn + a1xn-1 +... + an-1x + an, принимающий при x = 0 и x = 1 нечётные значения, не имеет целых корней.

4.6. Даны два многочлена от переменной x с целыми коэффициентами. Произведение их есть многочлен от переменной x с чётными коэффициентами, не все из которых делятся на 4. Докажите, что в одном из многочленов все коэффициенты чётные, а в другом хотя бы один нечётный.

40 Глава 4. Делимость 4.7. В числовом треугольнике каждое число равно сумме трёх чисел предыдущей строки:

1 1 1 2 3 2 1 3 6 7 6 3 1 4 10 16 19 16 10 4 Докажите, что в каждой строке, начиная с 3-й, найдутся чётные числа.

4.2. Алгоритм Евклида и основная теорема арифметики Натуральное число p > 1 называют простым, если его нельзя представить в виде произведения двух натуральных чисел, каждое из которых отлично от 1. Натуральное число n > 1 называют составным, если оно не простое. Если натуральное число n составное, то n = n1n2, где n1 < n и n2 < n. Поэтому любое натуральное число n > 1 можно разложить на простые множители. Это утверждение составляет лёгкую часть так называемой основной теоремы арифметики. Трудная часть основной теоремы арифметики однозначность такого разложения (с точности до перестановки множителей). Чтобы её доказать, можно воспользоваться алгоритмом Евклида, который часто бывает полезен и в других ситуациях.

Пусть a и b натуральные числа, причём a b. Тогда существуют целые неотрицательные числа q и r, для которых b = qa + r и r < a (деление с остатком). Алгоритм Евклида заключается в следующем.

Пусть a0 и a1 натуральные числа, причём a0 a1. Поделим a0 на a1 с остатком: a0 = q1a1 + a2; затем поделим a1 на a2 с остатком a1 = = q2a2 + a3, и т.д. В конце концов получим ak-1 = qkak. Все числа a0, a1,..., ak имеют вид ma0 + na1, где m и n целые числа. Поэтому, в частности, ak делится на любой общий делитель чисел a0 и a1. С другой стороны, ak-2 = qk-1ak-1 + ak = (qk-1qk + 1)ak, и т.д, поэтому числа a0 и a1 делятся на ak. Это означает, что ak наибольший общий делитель чисел a0 и a1. В частности, наибольший общий делитель чисел a0 и a1 можно представить в виде ma0 + na1, где m и n целые числа.

Алгоритм Евклида это алгоритм нахождения наибольшего общего делителя двух чисел. Наибольший общий делитель чисел a и b мы будем обозначать НОД(a, b).

4.8. Пусть a = bc и НОД(a, b) = 1. Докажите, что c делится на a.

Глава 4. Делимость 4.9. Докажите основную теорему арифметики.

21n + 4.10. Докажите, что дробь несократима ни при каких нату14n + ральных n.

4.11. Последовательность натуральных чисел a1, a2,... такова, что НОД(am, an) = НОД(am-n, an) для любых m > n. Докажите, что НОД(am, an) = ad, где d = НОД(m, n).

4.12. Докажите, что для любого натурального a и любых натуральных m и n НОД(am - 1, an - 1) = ad - 1, где d = НОД(m, n).

4.3. Разложения на простые множители 4.13. Пусть p/q несократимая дробь, p и q натуральные чис p p2qла. Положим f =, где q1,..., qn различные простые q q1... qn делители числа q. Докажите, что f взаимно однозначное отображение множества положительных рациональных чисел на множество всех натуральных чисел.

4.4. Признаки делимости 4.14. Пусть anan-1... a1a0 десятичная запись некоторого числа.

а) Докажите, что это число делится на 3 тогда и только тогда, когда a0 + a1 +... + an делится на 3.

б) Докажите, что это число делится на 9 тогда и только тогда, когда a0 + a1 +... + an делится на 9.

в) Докажите, что это число делится на 11 тогда и только тогда, когда a0 - a1 + a2 - a3 +... + (-1)nan делится на 11.

4.15. В десятичной записи целого числа есть 300 единиц, а остальные цифры нули. Может ли это число быть полным квадратом 4.16. Имеются семь жетонов с цифрами 1, 2, 3, 4, 5, 6, 7. Докажите, что ни одно семизначное число, составленное посредством этих жетонов, не делится на другое.

4.17. Пусть anan-1... a1a0 десятичная запись некоторого числа.

Заменим это число на anan-1... a1 + 2a0. Полученное число снова преобразуем по такому же правилу и т.д. до тех пор, пока не получится число, не превосходящее 19. Докажите, что исходное число делится на 19 тогда и только тогда, когда в итоге получается 19.

42 Глава 4. Делимость 4.18. Пусть anan-1... a1a0 десятичная запись некоторого числа.

Заменим это число на anan-1... a1 -2a0. Докажите, что исходное число делится на 7 тогда и только тогда, когда полученное число делится на 7.

4.5. Наибольший общий делитель и наименьшее общее кратное ab 4.19. а) Докажите, что НОД(a, b) =.

НОК(a, b) abc НОК(a, b, c) б) Докажите, что НОД(a, b, c) =. (ОбНОК(a, b) НОК(b, c) НОК(c, a) щая формула приведена в задаче 14.26.) abc НОД(a, b, c) в) Докажите, что НОК(a, b, c) =.

НОД(a, b) НОД(b, c) НОД(c, a) 4.20. Докажите, что НОД(a, НОД(b, c)) = НОД(НОД(a, b), c) = = НОД(a, b, c).

НОК(a, a + b) a + b 4.21. Докажите, что =.

НОК(a, b) b 4.22. Натуральные числа a и b взаимно просты. Докажите, что НОД(a + b, a2 + b2) = 1 или 2.

4.23. Докажите, что наибольший общий делитель суммы двух чисел и их наименьшего общего кратного равен наибольшему общему делителю самих чисел.

4.24. Докажите, что наименьшее общее кратное n натуральных чисел a1 < a2 <... < an не меньше na1.

4.25. Функция f(a, b), определённая для всех натуральных a и b, обладает следующими свойствами: (1) f(a, a) = a; (2) f(a, b) = f(b, a);

(3) (a + b)f(a, b) = bf(a, a + b). Докажите, что f(a, b) = НОК(a, b).

4.26. Дано несколько натуральных чисел, каждое из которых меньше натурального числа N 4. Наименьшее общее кратное любых двух из них больше N. Докажите, что сумма обратных величин этих чисел меньше 2.

4.6. Делимость нацело 4.27. Докажите, что 72n - 52n делится на 24.

Глава 4. Делимость n5 n3 7n 4.28. Докажите, что + + целое число для любого нату5 3 рального n.

4.29. При каких целых n число 20n + 16n - 3n - 1 делится на 323 4.30. Докажите, что если при любом натуральном k = b число a-kn делится на b-k, то a = bn. (Здесь a, b, n фиксированные натуральные числа.) n 4.31. Докажите, что если 2n - 2 делится на n, то 22 -1 - 2 делится на 2n - 1.

4.32. Пусть a, b, m и n натуральные числа, причём a взаимно просто с b и a > 1. Докажите, что am + bm делится на an + bn тогда и только тогда, когда m = kn, где k нечётное число.

* * * 1 1 4.33. а) Докажите, что число + +... + не может быть целым.

2 3 n 1 1 б) Докажите, что число + +... +, где k и n натуk k + 1 k + n ральные числа, не может быть целым.

4.34. Докажите, что следующие числа являются целыми:

(m + n)! (2m)!(2n)! а) ; б) ;

m!n! m!n!(m + n)! (5m)!(5n)! (3m + 3n)!(3n)!(2m)!(2n)! в) ; г).

m!n!(3m + n)!(3n + m)! (2m + 3n)!(m + 2n)!m!(n!)2(m + n)! 4.7. Делимость на степень простого числа 4.35. Сколькими нулями оканчивается произведение всех целых чисел от 1 до 100 включительно 4.36. Пусть p простое число и a наибольшее целое число, для которого n! делится на pa. Докажите, что n n n a = + + +...

p p2 p4.37. Докажите, что n! не делится на 2n.

4.38. Найдите наибольшую степень двойки, на которую делится число (n + 1)(n + 2)... 2n.

44 Глава 4. Делимость * * * 1 4.39. Найдите все натуральные n, для которых и конечные n n + десятичные дроби.

4.40. а) Докажите, что для любого нечётного числа a и любого натурального числа m существует бесконечно много натуральных чисел k, для которых ak - 1 делится на 2m.

б) Докажите, что для любого нечётного числа a существует лишь конечное число натуральных чисел m, для которых am - 1 делится на 2m.

4.41. Найдите все натуральные числа m, для которых: а) 3m - делится на 2m; б) 31m - 1 делится на 2m.

4.8. Остатки от деления 4.42. Какие остатки может давать квадрат целого числа при делении на: а) 3, б) 4, в) 5, г) 8 4.43. Найдите наименьшее натуральное число, которое:

а) При делении на 5 даёт остаток 4, при делении на 6 остаток 5, а при делении на 7 остаток 6.

б) При делении на 5 даёт остаток 4, при делении на 6 остаток 5, а при делении на 8 остаток 7.

4.44. Найдите число, которое:

а) При делении на 5 даёт остаток a, а при делении на 6 остаток b.

б) При делении на 5 даёт остаток a, при делении на 6 остаток b, а при делении на 7 остаток c.

4.45. а) Число n при делении на 4 даёт остаток 3. Докажите, что n нельзя представить в виде суммы двух квадратов целых чисел.

б) Число n при делении на 8 даёт остаток 7. Докажите, что n нельзя представить в виде суммы трёх квадратов целых чисел.

4.46. Найдите четырёхзначное число, которое при делении на даёт в остатке 112, а при делении на 132 даёт в остатке 98.

4.47. Допишите к 523... три цифры так, чтобы полученное шестизначное число делилось на 7, 8 и 9.

4.48. Найдите остаток от деления на 7 числа 2 3 1010 + 10(10 ) + 10(10 ) +... + 10(10 ).

Глава 4. Делимость 4.49. Пусть числа m1,..., mk попарно взаимно простые и m = = m1... mk. Докажите, что для любых целых чисел a1,..., ak система сравнений x ai (mod mi), где i = 1,..., k, имеет решение, причём если x1 и x2 два решения, то x1 - x2 делится на m (китайская теорема об остатках ).

4.50. Найдите все натуральные числа n, для которых 2n - 1 делится на 7.

4.51. Пусть p простое число. Предположим, что дано r натуральных чисел a1,..., ar, меньших p. Докажите, что если r < p, то из данных чисел можно составить по крайней мере r+1 сумм, дающих разные остатки при делении на p (допускается и сумма пустого множества слагаемых, которая считается равной нулю).

4.52. Докажите, что из любых 2n - 1 целых чисел можно выбрать ровно n чисел, сумма которых делится на n.

4.9. Взаимно простые числа Натуральные числа m и n называют взаимно простыми, если НОД(m, n) = 1.

4.53. Докажите, что ни для какого натурального n число n(n + 1) не может быть степенью натурального числа.

4.54. а) Докажите, что каково бы ни было целое число n, среди чисел n, n + 1, n + 2, n + 3, n + 4 есть хотя бы одно число, взаимно простое с остальными четырьмя из этих чисел.

б) Докажите, что каково бы ни было целое число n, среди чисел n, n + 1, n + 2,..., n + 9 есть хотя бы одно число, взаимно простое с остальными девятью из этих чисел.

4.55. Пусть n и m различные натуральные числа. Докажите, что n-1 m-числа Fn = 22 + 1 и Fm = 22 + 1 взаимно простые.

4.10. Простые числа 4.56. Докажите, что квадрат любого простого числа p > 3 при делении на 12 даёт в остатке 1.

4.57. Докажите, что существует бесконечно много простых чисел (Евклид).

4.58. Докажите, что существует бесконечно много простых чисел вида 4k - 1.

46 Глава 4. Делимость 4.59. а) Докажите, что если число 2n - 1 простое, то число n тоже простое.

б) Докажите, что если число 2n + 1 простое, то n = 2k.

n n-4.60. Докажите, что при любом натуральном n число 22 + 22 + имеет не менее n различных простых делителей.

4.11. Арифметика остатков 4.61. Докажите, что остатки от деления на n чисел a b и ab однозначно задаются остатками от деления на n чисел a и b.

4.62. Пусть p простое число, а число a не делится на p. Докажите, что все остатки от деления на p чисел a, 2a, 3a,..., (p-1)a попарно различны, т.е. каждое число от 1 до p - 1 встречается среди этих остатков ровно один раз.

4.63. Докажите, что если p простое число, а числа a и b не делятся на p, то остаток от деления на p числа a однозначно определяется остатками от деления чисел b и ab на p.

Решения 4.1. О т в е т: нельзя. Чётность числа 1 2 3 ... 10 не зависит от выбора знаков; она зависит только от того, сколько в этом выражении нечётных чисел. В этом выражении 5 нечётных чисел, поэтому оно всегда будет нечётно.

4.2. Сопоставим делителю d числа n делитель n/d. Если для всех d числа d и n/d разные (т.е. n = d2), то делители числа n разбиваются на пары, поэтому их чётное число. Если же n = d2, то все делители, отличные от d, разбиваются на пары, поэтому их нечётное число.

4.3. Предположим, что все числа ak - bk нечётны. Тогда число (a1 - b1) + +... + (a2n+1 - b2n+1) тоже нечётно (сумма нечётного числа нечётных чисел нечётна). Но это число равно 0, поскольку a1 +... + a2n+1 = b1 +... + b2n+1.

4.4. Предположим, что числа a, b, c нечётны и ax2 + bx + c = 0 для некоторого рационального числа x = m/n, где числа m и n взаимно простые.

Из равенства am2 + bmn + cn2 = 0 следует, что число m2 + mn + n2 чётно. Но числа m и n либо оба нечётны, либо одно из них чётно, а другое нечётно. В обоих случаях число m2 + mn + n2 нечётно.

4.5. Пусть P (x) = a0xn + a1xn-1 +... + an-1x + an. По условию числа an = P (0) и a0 + a1 +... + an = P (1) нечётны. Если x чётное число, то P (x) an (mod 2). Если x нечётное число, то P (x) a0 + a1 +... + an Глава 4. Делимость (mod 2). В обоих случаях получаем, что число P (x) нечётно, поэтому оно не может быть равно нулю.

4.6. Из того, что не все коэффициенты произведения делятся на 4, следует, что у одного многочлена есть нечётный коэффициент. Нужно доказать, что у другого многочлена нет нечётных коэффициентов. Предположим, что у обоих многочленов есть нечётные коэффициенты. Заменим каждый коэффициент на его остаток от деления на 2. В результате получим многочлены anxn + an-1xn-1 +... + xr и bmxm + bm-1xm-1 +... + xs. Если в произведении данных многочленов мы заменим каждый коэффициент на его остаток от деления на 2, то получим многочлен anbmxn+m +... + xr+s. Таким образом в произведении данных многочленов коэффициент при xr+s нечётен, что противоречит условию.

4.7. Выпишем в каждой строке, начиная с третьей, первые четыре числа, заменив каждое чётное число на 0, а нечётное на 1:

1 0 1 1 1 0 1 0 0 1 1 1 1 0 1....

Пятая выписанная строка совпала с первой, поэтому в дальнейшем первые четыре числа будут периодически повторяться. Остаётся заметить, что в каждой из первых пяти выписанных строк есть чётные числа.

4.8. Пусть m и n натуральные числа, для которых ma + nb = = НОД(a, b) = 1. Тогда mac + nbc = c, т.е. a(mc + n) = c. Это означает, что c делится на a.

4.9. Предположим, что a = p1... pr = q1... qs, где p1,..., pr, q1,..., qs простые числа. Ясно, что либо НОД(p1, q1) = 1, либо НОД(p1, q1) = p1 и p1 = q1. Если НОД(p1, q1) = 1, то согласно задаче 4.8 число q2... qs делится на p1. Если при этом НОД(p1, q2) = 1, то число q3... qs делится на p1 и т.д.

Pages:     | 1 |   ...   | 3 | 4 | 5 | 6 | 7 |   ...   | 65 |    Книги по разным темам