Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
4.7. Делимость на степень простого числа. Сколькими нулями оканчивается произведение всех целых чисел от 1 до 100 включительно. Пусть p — простое число и a — наибольшее целое число, для которого n! делится на p a . Докажите, что+ . . . 4.37. Докажите, что n! не делится на 2 n 4.38. Найдите наибольшую степень двойки, на которую делится число (n + 1)(n + 2) · . . . · 2n. * * * 4.39. Найдите все натуральные n, для которых 1 n и 1 n +1 — конечные десятичные дроби. а) Докажите, что для любого нечётного числа и любого натурального числа m существует бесконечно много натуральных чисел k, для которых a k − 1 делится наб) Докажите, что для любого нечётного числа a существует лишь конечное число натуральных чисел m, для которых a m − 1 делится на 2 m 4.41. Найдите все натуральные числа m, для которых: а) 3 m − 1 делится наб делится на 2 m Глава 4. Делимость. Остатки отделения. Какие остатки может давать квадрат целого числа при делении на а) 3, б) 4, в) 5, г) 8? 4.43. Найдите наименьшее натуральное число, которое: а) При делении на 5 даёт остаток 4, при делении на 6 остаток 5, а при делении на 7 — остаток б) При делении на 5 даёт остаток 4, при делении на 6 остаток 5, а при делении на 8 — остаток 7. 4.44. Найдите число, которое: а) При делении на 5 даёт остаток a, а при делении на 6 остаток б) При делении на 5 даёт остаток a, при делении на 6 остаток b, а при делении на 7 — остаток c. 4.45. а) Число n при делении на 4 даёт остаток 3. Докажите, что n нельзя представить в виде суммы двух квадратов целых чисел. б) Число n при делении на 8 даёт остаток 7. Докажите, что n нельзя представить в виде суммы трёх квадратов целых чисел. Найдите четырёхзначное число, которое приделе- нии на 131 даёт в остатке 112, а при делении на 132 даёт в остатке 98. 4.47. Допишите к 523 . . . три цифры так, чтобы полученное шестизначное число делилось на 7, 8 и 9. 4.48. Найдите остаток отделения на 7 числа 10 + 10 (10 2 ) + 10 (10 3 ) + . . . + 10 (10 10 ) 4.49. Пусть числа m 1 , . . ., попарно взаимно простые и m=m 1 . . . m k . Докажите, что для любых целых чисел a 1 , . . . . . . , система сравнений x ≡ a i (mod m i ), где i = 1, . . . . . . , k, имеет решение, причём если и x 2 — два решения, то x 1 − делится на m китайская теорема об остатках. Найдите все натуральные числа n, для которых 1 делится на 7. Условия задач. Пусть p — простое число. Предположим, что дано натуральных чисел a 1 , . . ., a r , меньших p. Докажите, что если r < p, то изданных чисел можно составить по крайней мере r + 1 сумм, дающих разные остатки при делении на p допускается и сумма пустого множества слагаемых, которая считается равной нулю. Докажите, что из любых 2n − 1 целых чисел можно выбрать ровно n чисел, сумма которых делится на n. 4.9. Взаимно простые числа Натуральные числа m и n называют взаимно простыми, если НОД(m, n) = 1. 4.53. Докажите, что ни для какого натурального n число+ 1) не может быть степенью натурального числа. а) Докажите, что каково бы ни было целое число, среди чисел n, n + 1, n + 2, n + 3, n + 4 есть хотя бы одно число, взаимно простое с остальными четырьмя числами. б) Докажите, что каково бы ни было целое число n, среди чисел n, n + 1, n + 2, . . ., n + 9 есть хотя бы одно число, взаимно простое с остальными девятью числами. Пусть n и m — различные натуральные числа. Докажите, что числа F n = 2 2 n−1 + 1 и F m = 2 2 m−1 + 1 взаимно простые. Простые числа. Докажите, что квадрат любого простого числа p > при делении на 12 даёт в остатке 1. 4.57. Докажите, что существует бесконечно много простых чисел (Евклид. Докажите, что существует бесконечно много простых чисел вида 4k − 1. 4.59. а) Докажите, что если число 2 n − 1 простое, то число тоже простое. б) Докажите, что если число 2 n + 1 простое, то n = 2 k Глава 4. Делимость. Докажите, что при любом натуральном n число 2 n + 2 2 n−1 + 1 имеет не менее n различных простых делителей. Арифметика остатков. Докажите, что остатки отделения на n чисел a ± и ab однозначно задаются остатками отделения на n чисел и b. 4.62. Пусть p — простое число, а число a не делится на p. Докажите, что все остатки отделения на p чисел a, 2a, 3a, . . ., (p − 1)a попарно различны, те. каждое число от 1 до p − 1 встречается среди этих остатков ровно один раз. Докажите, что если p — простое число, а числа и b не делятся на p, то остаток отделения на p числа однозначно определяется остатками отделения чисел b и на Решения. Ответ нельзя. Чётность числа 1 ± 2 ± 3 ± . . . ± 10 не зависит от выбора знаков она зависит только оттого, сколько в этом выражении нечётных чисел. В этом выражении 5 нечётных чисел, поэтому оно всегда будет нечётно. 4.2. Сопоставим делителю d числа n делитель n/d. Если для всех d числа d и n/d разные те, то делители числа разбиваются на пары, поэтому их чётное число. Если же n = то все делители, отличные от d, разбиваются на пары, поэтому их нечётное число. Предположим, что все числа a k − b k нечётны. Тогда число b 1 ) + . . . + (a 2n+1 − b 2n+1 ) тоже нечётно (сумма нечётного числа нечётных чисел нечётна). Но это число равно 0, поскольку a 1 + . . . . . . + a 2n+1 = b 1 + . . . + b 2n+1 4.4. Предположим, что числа a, b, c нечётны и ax 2 + bx + c = для некоторого рационального числа x = m/n, где числа m и n взаимно простые. Из равенства am 2 + bmn + cn 2 = 0 следует, что число+ mn + n 2 чётно. Но числа m и n либо оба нечётны, либо одно из Решения задач 51 них чётно, а другое нечётно. В обоих случаях число m 2 + mn + n 2 нечётно. 4.5. Пусть P(x) = a 0 x n + a 1 x n −1 + . . . + a n −1 x + a n . По условию числа a n = P(0) и a 0 + a 1 + . . . + a n = P(1) нечётны. Если x — чёт- ное число, то P(x) ≡ a n (mod 2). Если x — нечётное число, то a 0 + a 1 + . . . + a n (mod 2). В обоих случаях получаем, что число P(x) нечётно, поэтому оно не может быть равно нулю. Из того, что не все коэффициенты произведения делятся наследует, что у одного многочлена есть нечётный коэффициент. Нужно доказать, что у другого многочлена нет нечёт- ных коэффициентов. Предположим, что у обоих многочленов есть нечётные коэффициенты. Заменим каждый коэффициент на его остаток отделения на 2. В результате получим многочлены a n x n + + a n −1 x n −1 + . . . + и b m x m + b m −1 x m −1 + . . . + x s . Если в произведении данных многочленов мы заменим каждый коэффициент на его остаток отделения на 2, то получим многочлен+ . . . + x r +s . Таким образом, в произведении данных многочленов коэффициент при x r +s нечётен, что противоречит условию. Выпишем в каждой строке, начиная с третьей, первые четыре числа, заменив каждое чётное число на 0, а нечётное — на 1: 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 Пятая выписанная строка совпала с первой, поэтому в дальнейшем первые четыре числа будут периодически повторяться. Оста- ётся заметить, что в каждой из первых пяти выписанных строк есть чётные числа. Пусть m и n — натуральные числа, для которых ma + nb = =НОД(a, b)=1. Тогда mac+nbc=c, те, где число натуральное. Это означает, что c делится на a. 4.9. Предположим, что a = p 1 . . . p r = q 1 . . . q s , где p 1 , . . . , p r , q 1 , . . . , q s — простые числа. Ясно, что либо НОД(p 1 , q 1 ) = 1, либо НОД(p 1 , q 1 ) = и p 1 = q 1 . Если НОД(p 1 , q 1 ) = 1, то согласно задаче 4.8 число q 2 . . . делится на p 1 . Если при этом НОД(p 1 , q 2 ) = = 1, то число q 3 . . . делится на и т. д. В конце концов получим q i . После этого доказательство завершается очевидной индукцией Глава 4. Делимость. Найдём наибольший общий делитель чисел 21n + и 14n + 3, пользуясь алгоритмом Евклида. Поделив 21n + 4 на + 3, получим в остатке 7n + 1. Поделив 14n + 3 на 7n + получим в остатке 1. Значит, числа 21n + 4 и 14n + 3 взаимно простые. Для любой пары натуральных чисел {m, n}, где m > последовательные операции {m, n} → {m − n, n} приводят к паре, d}, где d =НОД(m, n). Действительно, операция деления m нас остатком состоит из нескольких таких операций. Согласно задаче 4.11 достаточно проверить, что НОД(a m − −1, a n −1)=НОД(a m −n −1, a n −1) для любых m>n> 1. Но a m −1= = a n (a m −n − 1) + a n − 1 и числа a и a n − 1 взаимно простые. Пусть p = p a 1 1 . . . p a m m , q = q b 1 1 . . . q b n n . Тогда f(p/q) = p 2a 1 1 . . . . . . p 2a m m q 2b 1 −1 1 . . . q 2b n −1 n . Ясно, что каждое натуральное число представимо в таком виде ровно одним способом. а) Число 10 при делении на 3 даёт остаток 1. Поэтому при делении на 3 тоже даёт остаток 1. Следовательно, при делении на 3 даёт остаток б) Решение аналогично решению задачи а). в) Число 10 при делении на 11 даёт остаток −1. Поэтому при делении на 11 даёт остаток (−1) k . Следовательно, при делении на 11 даёт остаток (−1) k a k 4.15. Это число делится на 3, ноне делится на 9, поэтому оно не может быть полным квадратом. Пусть a и b — семизначные числа, составленные посредством этих жетонов. Предположим, что a делится на b и a 6= Тогда a − b тоже делится на b. Ясно, что b b 6 7. С другой стороны делится на 9, а b не делится на 9. Поэтому делится на 9. Приходим к противоречию. Мы заменяем число 10a + b на a + 2b. Для любого числа + b, большего 19, имеет место неравенство 9a > b, те. Поэтому при указанных преобразованиях число всегда уменьшается. Ясно, что 10a + b делится на 19 тогда и только тогда, когда 20a + 2b делится нате делится на 19. 4.18. Запишем исходное число в виде 10a + a 0 . Нужно доказать, что оно делится на 7 тогда и только тогда, когда a − делится на 7. Ясно, что 10a + делится на 7 тогда и только тогда, когда 20a + делится на 7. Остаётся заметить, что при делении на 7 число 20a + дат такой же остаток, как и число + 2a 0 Решения задача) Пусть a = p a 1 1 . . . и b = p b 1 1 . . . p b k k . Тогда НОД(a, b) = p min{ a 1 , b 1 } 1 . . . p min{ a k , b k } k , НОК(a, b) = p max{ a 1 , b 1 } 1 . . . Поэтому доказательство можно провести для каждого простого множителя отдельно. Если a=p a и b=p b , причём a 6 b , то НОД(a, b)=p a и ab НОК(a, b) = = p a p b p b = p a б) Достаточно рассмотреть случай, когда a = p a , b = p b , c = p g , причём a 6 b 6 g . В этом случае НОД(a, b, c) = p a , abc НОК(a, b, c) НОК(a, b) НОК(b, c) НОК(c, a) = p a p b p g p g p b p g p g = p a в) Достаточно заметить, что p g 4.20. Пусть наибольшая степень простого числа p, на которую делятся a, b, c, равна a , b , g . Требуется доказать, что min( a , min( b , g )) = min(min( a , b ), g )) = где min(x, y) — наименьшее из чисел x и y. Это утверждение о наименьших числах очевидно. Согласно задаче 4.19 а+ b) НОК(a, b) = (a + b)ab НОД(a, b) = (a + b)ab НОД(a, a + b) = b НОК(a, a + b). 4.22. Предположим, что числа a+b и a 2 + делятся на d. Тогда число 2ab = (a + b) 2 − (a 2 + b 2 ) тоже делится на d. Поэтому числа 2a(a + b) − 2ab и 2b 2 = 2b(a + b) − 2ab тоже делятся на d. По условию числа a и b взаимно просты, поэтому числа и тоже взаимно просты. Значит, d = 1 или 2. 4.23. В наименьшее общее кратное чисел a и b входят только те простые делители, которые входят в a и b. Только они и могут входить в наибольший общий делитель суммы и наименьшего общего кратного. Поэтому достаточно проследить за степенью каждого простого множителя отдельно. Пусть a = p a . . . и b = p b . . . , причём a 6 b . Тогда сумма чисел a и b имеет вида их наименьшее общее кратное имеет вид p b . . . Поэтому рассматриваемый Глава 4. Делимость наибольший общий делитель имеет вид p a . . . Наибольший общий делитель самих чисел a и b имеет такой же вид. Пусть наименьшее общее кратное данных чисел равно Тогда. . . > a a n — различные натуральные числа. Поэтому, те. Функция f(a, b) = НОК(a, b) обладает свойствами (свойства (1) и (2) очевидны, а свойство (3) доказано в задаче Легко видеть, что свойства (2) и (3) позволяют вычислить f(a, если известны значения f(a 1 , b 1 ) для всех натуральных и для которых a 1 + b 1 < a + b. Поэтому функция f(a, b) единственна. Пусть a 1 , . . . , a n — данные числа. Количество членов ряда, 2, 3, . . . , N, делящихся на a k , равно h N a k i . По условию наименьшее общее кратное любых двух из чисел a 1 , . . . , больше поэтому среди чисел 1, 2, . . . , N нет ни одного числа, делящегося одновременно на два из чисел a 1 , . . . , a n . Поэтому число членов последовательности 1, 2, . . . , N, делящихся хотя бы на одно из чисел a 1 , . . . , a n , равно h N a 1 i + h N a 2 i + . . . Нов последовательности 1, 2, . . . , N всего N членов, поэтому h N a 1 i + h N a 2 i + . . . Учитывая, что h N a k i > N a k − 1, получаем 1 ” + “ N a 2 − 1 ” + . . . + “ N a n − те Сокращая обе части на N, получаем требуемое. Число a n − делится на a − b задача 5.1 а, поэтому 2n − 5 делится на 7 2 − 5 2 = 24. 4.28. Нужно доказать, что 3n 5 + 5n 3 + 7n делится нате делится на 3 и 3n 5 + 7n делится на 5. Ясно, что 5n 3 + 7n ≡ ≡ −(n 3 − n) (mod 3) и 3n 5 + 7n ≡ −2(n 5 − n) (mod 5). Рассматривая все различные остатки, легко проверить, что n 3 − n делится на а n 5 − n делится на 5. Решения задач 55 |