Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
4.29. О т в е т прич тных n. Прежде всего заметим, что = 17 · 19, поэтому число делится на 323 тогда и только тогда, когда оно делится на 17 и на 19. Число 20 n − делится на − 3 = 17. Далее, 16 n ≡ (−1) n (mod 17), поэтому число 16 n − делится на 17 тогда и только тогда, когда n чётно. Что касается делимости на 19, то 20 n − 1 делится на 20 − 1 = 19 при любом а при n = 2m число 16 n − делится на 16 2 − 3 2 = 13 · 19, поэтому оно делится на 19. 4.30. Многочлен x n − делится на x − y задача 5.1 а, поэтому делится на b − k. Значит, число a − b n = (a − k n ) − (b n − делится на b − k при любом k 6= b. Это возможно лишь в том случае, когда a = b n 4.31. Пусть 2 n − 2 = nm. Тогда 2 n −1 − 2 2 n − 1 = 2 2 2 n −2 − 1 2 n − 1 = 2 2 nm − 1 2 n − 1 = 2(2 n(m −1) + 2 n(m −2) + . . . + 2 n + 1). 4.32. Если m = kn, где k — нечётное число, то a m + b m = (a n ) k + + делится на a n + задача 5.1 б). Пусть m = kn + r, где k — нечётное число и 0 < r < n. Докажем, что a m + не делится на a n + b n . Действительно+ b kn +r = a r (a kn + b kn ) + b kn (b r − Здесь a r (a kn + b kn ) делится на a n + b n , а b kn (b r − a r ) не делится на, поскольку взаимно просто си Пусть m = ln + r, где l — чётное число и 0 6 r < n. Докажем, что a m + не делится на a n + b n . Действительно, пусть k = l − 1 (k — нечётное число. Тогда+ b ln +r = a kn a n +r + b kn b n +r = = a n +r (a kn + b kn ) + b kn +r (a n + b n ) − b kn a n (a r + Здесь первые два слагаемых делятся на a n + b n , а последнее не делится, поскольку взаимно просто си. Решим сразу задачу б. Предположим, что рассматриваемое число целое. Выберем среди чисел k, k+1, . . . , k+n те, которые делятся на наибольшую степень двойки. Пусть такое число только одно, а именно, 2 m p, где p нечётно. Тогда рассматриваемое число имеет вид 2 m “ 1 p + 2q r ” = r + 2qp 2 m pr , где числа p и r нечётные. Это число представляет собой дробь с нечётным знаменателем и чётным числителем такое число не может быть целым. Поэтому есть по крайней мере два числа, которые делятся на максимальную степень двойки, а именно, 2 m p и 2 m q, где p < q Глава 4. Делимость и p, q — нечётные числа. Но тогда p + 1 < q и p + 1 — чётное число. Поэтому число 2 m (p + 1) содержится среди чисел k, k + 1, . . . , k + и делится на 2 m +1 , что противоречит выбору числа m. 4.34. Рассмотрим общее выражение+ b k n)!) d k , где и b k — целые неотрицательные числа, d k — целые числа. Наивысшая степень простого числа p, на которую делится число n!, равна (задача 4.36). Поэтому если для любых чисел x, y > выполняется неравенство+ b k y ] > 0, то рассматриваемое выражение является целым числом. В задачах а)––г) числа a k , b k , связаны соотношением 0. В таком случае функция f(x, y) = P k d k (a k x + обладает следующим свойством f(x + 1, y) = f(x, y) = f(x, y + Поэтому неравенство f(x, y) > 0 достаточно проверить для чисел, y, удовлетворяющих неравенствам 0 6 x, y < а) Нужно доказать неравенство [x + y] − [x] − [y] > 0 для 06 x, y < < 1. Но [x] = [y] = б) Нужно доказать неравенство [2x] + [2y] − [x] − [y] − [x + y] > для 0 6 x, y < 1. Учитывая, что [x] = [y] = 0, переходим к неравен 1 0 1 0 Рис. 4.1. Графики в квадрате б) ству f(x, y) = [2x] + [2y] − [x + y] > 0. Чтобы вычислить значения функции f(x, в квадрате 0 6 x, y < 1, поступим следующим образом. Нарисуем графики 2x = и 2y = 1 сплошными линиями, а график+ y = 1 пунктирной линией (рис. Ясно, что f(0, 0) = 0; поэтому f = и во всех точках фигуры, ограниченной этими графиками и сторонами квадрата и содержащей начало координат. При переходе через сплошную линию значение функции f увеличивается на а при переходе через пунктирную линию уменьшается на 1 (имеется ввиду движение в направлении от начала координат. Это замечание позволяет вычислить значения функции f(x, y) во всех точках квадрата и убедиться, что они неотрицательны. На рис. 4.1 эти значения выписаны. в) Нужно доказать неравенство f(x, y) = [5x] + [5y] − [3x + y] − − [x + 3y] > 0 для 0 6 x, y < 1. Чтобы вычислить значения функ- Решения задач 57 ции f(x, y) во всех точках квадрата, для каждого выражения+ b k y ] нарисуем графики a k x + b k y = 1, 2, . . . , a k + b k − для знака плюс график рисуем сплошной линией, а для знака минус — пунктирной (рис. 4.2). Затем пользуемся теми же правилами, что и при решении задачи б 1 0 1 0 2 1 1 0 2 1 0 1 0 2 1 1 0 1 1 0 1 2 1 1 0 1 0 0 2 1 1 0 2 1 2 1 2 1 1 1 0 1 2 1 2 1 1 0 1 2 1 2 1 0 2 1 0 1 2 1 2 1 Рис. 4.2. Графики в квадрате в) г) Нужно доказать неравенство f(x, y) = [3x + 3y] + [3y] + [2x] + +[2y]−[2x+3y]−[x+2y]−[x+y]>0. Это делается также, как и при Глава 4. Делимость 1 0 1 0 1 2 1 0 1 0 1 0 1 0 1 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 Рис. 4.3. Графики в квадрате г) решении задачи в, см. рис. 4.3. Отметим, что график x + y = мы не рисуем, потому что при прохождении через этот график значение функции f(x, y) увеличивается на 1 и уменьшается нате. не изменяется. Ответ. Среди чисел от 1 доесть чисел, делящихся на 5, а среди чисел, делящихся наесть числа, делящихся на 25 (чисел, делящихся на 125, среди данных чисел нет. Поэтому рассматриваемое произведение делится на 5 и не делится на 5 25 . Ясно также, что оно делится на 2 24 4.36. Среди чисел 1, 2, . . . , n есть [n/p] чисел, делящихся на p, [n/p 2 ] чисел, делящихся на p 2 , и т. д. Пусть a — наибольшее целое число, для которого n! делится на 2 a . Согласно задаче 4.36 a = h n 2 i + h n 2 2 i + h n 2 3 i + . . . 6 n 2 + n 2 2 + n 2 3 + . . . = поскольку [x] 6 x. Кроме того 0 при достаточно больших. Поэтому a < n. Решения задач. Пусть (2n−1)!!=1·3·5·7·. . .·(2n−1) и (2n)!!=2·4·6·. . .·2n. Ясно, что (2n)!=(2n−1)!! (2n)!! и (2n)!!=2 n n!. Поэтому (n +1)(n+2)×. . . . . . ×2n= (2n)! n! = (2n − 1)!! (2n)!! n! = 2 n (2n −1)!!, причём число (2n − 1)!! нечётно. 4.39. Ответ и 4. При n > 1 должны выполняться равенства n и 2 s 5 t = n + 1. Числа n и n + 1 взаимно простые, поэтому должно выполняться либо равенство 2 k + 1 = 5 t , либо равенство+ 1 = 2 s . Предположим, что 5 l + 1 = 2 s . Тогда число оканчивается на 6, поэтому s = 4m. Значит, 5 l = 2 4m − 1 = (2 2m − 1)(2 2m + Но числа 2 2m − 1 и 2 2m + 1 не могут одновременно делиться на Рассмотрим теперь уравнение 2 k + 1 = 5 t . Пусть t = 2 m s, где s нечётно. Тогда 1 = (5 2 m − 1)(5 2 m (s −1) + 5 2 m (s −2) + . . . + Второй множитель состоит из нечётного числа нечётных слагаемых, те. он нечётен. Значит, s = 1. Далее 2 m − 1 = (5 − 1)(5 + 1)(5 2 + 1) . . . (5 2 m−1 + Число 5 + 1 = 6 не является степенью двойки, поэтому m = 0. Это соответствует равенству 2 2 + 1 = 5. 4.40. а) Пусть k = 2 n . Тогда 1 = (a 2 n−1 − 1)(a 2 n−1 + 1) = = (a − 1)(a + 1)(a 2 + 1)(a 4 + 1) . . . (a 2 n−1 + Число a нечётно, поэтому в этом произведении есть n + 1 чётных сомножителей. Значит, a k − 1 делится на 2 n +1 . Таким образом, если k = и n > m − 1, то a k − 1 делится наб) Введём следующее обозначение если m = 2 n s, где число s не- чётно, то d(m) = n. Ясно, что a m − 1 = (a 2 n − 1)(a 2 n (s −1) + a 2 n (s −2) + . . . . . . + 1), где сумма во второй скобке состоит из нечётного числа нечётных слагаемых. Поэтому d(a m − 1) = d(a 2 n − 1). Далее, враз- ложении (1) числа a 2 + 1, . . . , a 2 n−1 + 1 делятся на 2 и не делятся на 4, поскольку квадрат нечётного числа даёт остаток 1 приделе- нии на 4. Значит 1) = ( d(a − при n = 0; d(a 2 − 1) + n − 1 при n > Число a m − 1 делится на тогда и только тогда, когда d(a m − −1)> m. Разберём два случая. Если d(m)=0, те. число m нечётно, то должно выполняться неравенство m 6 d(a − 1). Это неравенство Глава 4. Делимость имеет конечное число нечётных решений. Если d(m) > 1, те. число чётно, то должно выполняться неравенство d(a 2 − 1) + n − 1 > > m = 2 n s, где n = d(m). Это неравенство можно переписать в виде 6 d(a 2 − 1) + n − 1 число s нечётно). Такое неравенство имеет конечное число решений, поскольку последовательность стремится к нулю при n → ∞ (задача 25.18). 4.41. а) Ответ и 4. Воспользуемся решением задачи б. Если a = 3, то d(a − 1) = 1 и d(a 2 − 1) = 3. Неравенство 6 2 + имеет следующие решения (s, n) = (1, 1) и (1, 2). б) О т в е т 1, 2, 4, 6 и 8. Если a = 31, то d(a − 1) = и d(a 2 − 1) = d(30 · 32) = 6. Неравенство s 6 5 + имеет следующие решения (s, n) = (1, 1), (3, 1), (1, 2) и (1, 3). (Напомним, что число s нечётно.) 4.42. а) Ответ и 1. Воспользуйтесь равенством (3k ± 1) 2 = = 9k 2 ± 6k + б) Ответ и 1. Воспользуйтесь равенством (2k + 1) 2 = 4k 2 + + 4k + в) Ответ и 4. Воспользуйтесь равенствами (5k ± 1) 2 = = 25k 2 ± 10k + 1 и (5k ± 2) 2 = 25k 2 ± 20k + г) Ответ и 4. Воспользуйтесь равенствами (2k + 1) 2 = = 4k(k + 1) + 1 и (4k + 2) 2 = 16k 2 + 16k + 4 и заметьте, что число+ 1) чётно. 4.43. а) Ответ. Пусть n — искомое число. Тогда n + делится на 5 · 6 · 7 = 210. Поэтому n = б) Ответ. Пусть n — искомое число. Тогда n + 1 делится на НОК(5, 6, 8) = 120. Поэтому n = 119. 4.44. а) Ответ. Пусть 6n≡1(mod 5) и 5m≡1(mod Тогда + 5mb ≡ 6na ≡ a (mod 5) 6na + 5mb ≡ 5mb ≡ b (mod В нашем случае m = 5 и n = б) Ответ. Пусть 42k ≡ 1 (mod 5), 35n ≡ ≡ 1 (mod 6) и 30m ≡ 1 (mod 7) здесь 42 = 6 · 7, 35 = 5 · 7, 30 = 5 · Тогда + 35nb + 30mc ≡ 42ka ≡ a (mod 5), 42ka + 35nb + 30mc ≡ 35nb ≡ b (mod 6), 42ka + 35nb + 30mc ≡ 30mc ≡ c (mod В нашем случае k = 3, n = 5, m = 4. Решения задача) Согласно задаче 4.42 б) сумма квадратов двух чисел при делении на 4 может давать остатки 0, 1 и б) Согласно задаче 4.42 г) сумма квадратов двух чисел при делении на 8 может давать остатки 0, 1, 2, 4 и 5, а сумма квадратов трёх чисел — остатки 0, 1, 2, 3, 4, 5 и 6. 4.46. Ответ. Пусть N — искомое число. По условию 131k + 112 = 132l + 98, где k и l — натуральные числа. Кроме того, N < 10 000, поэтому l = N − 98 132 < 10 000 − 98 132 6 75. Далее + 112 = 132l + 98, поэтому 131(k − l) = l − 14. Следовательно, если k 6= l, то |l − 14| > 131. Но l 6 75, поэтому k = l и l − 14 = Таким образом, N = 131 · 14 + 112 = 132 · 14 + 98 = 1946. 4.47. Ответили Полученное число должно делиться на 7 · 8 · 9 = 504. Поделим 000 нас остатком 523 000 = 1037 · 504 + 352. Поскольку − 352 = 152, на 504 делятся числа 523 152 и 523 152 + 504 = = 523 656. Других чисел, делящихся на 504, среди чисел от 000 до 523 999 нет. 4.48. О т в е т 5. Заметим, что 10 6 ≡ 1 (mod 7), поскольку 3 + 1 делится на 7, и 10 k ≡ 4 (mod 6) при k > 1, поскольку число чётно и делится на 3. Значит, 10 10 k ≡ 10 4 (mod 7) при > 1. Поэтому требуемый остаток равен остатку отделения числа · 10 4 = 10 на 7. Этот остаток равен 5. 4.49. Положим n i = m/m i . Число является произведением чисел, взаимно простых с m i , поэтому НОД(n i , m i ) = 1. В таком случае можно выбрать целые числа итак, что r i m i + s i n i = доказательство этого утверждения с помощью алгоритма Евклида приведено нас. Положим e i = и x = a 1 e 1 + . . . + Ясно, что e i ≡ 1 (mod m i ) и e i ≡ 0 (mod m j ) при j 6= i, поэтому a i (mod m i ), i = 1, . . . , Если и x 2 — решения рассматриваемой системы сравнений, то x 1 − x 2 ≡ 0 (mod m i ), i = 1, . . . , k. Числа m 1 , . . . , попарно взаимно простые, поэтому x 1 − делится на m. 4.50. Ясно, что 2 3 = 8 ≡ 1 (mod 7). Поэтому 2 3k ≡ 1 (mod 7), 2 3k+1 ≡ 2 (mod 7) и 2 3k+2 ≡ 4 (mod 7). Следовательно, 2 n − 1 делится на 7 тогда и только тогда, когда n делится на 3. 4.51. Применим индукцию по r. При r = 1 есть две суммы и a 1 . Предположим, что утверждение верно для r < p − 1 чисел и неверно для r + 1 чисел. Тогда суммы 0, s 1 , . . . , s r , составленные из чисел a 1 , . . . , a r , дают разные остатки при делении на p, но все суммы 0 + a r +1 , s 1 + a r +1 , . . . , s r + при делении на p не дают новых остатков по сравнению с 0, s 1 , . . . , s r . Значит, a r +1 ≡ s i (mod p) Глава 4. Делимость для некоторого i. Далее, s i + a r +1 ≡ s j (mod p) для некоторого те. Аналогично получаем, что остатки отделения на p чисел a r +1 , 2a r +1 , 3a r +1 , . . . , (p − содержатся среди остатков отделения на p чисел 0, s 1 , . . . , s r . Число p простое, и не делится на p. Поэтому остатки отделения на p чисел, 2a r +1 , . . . , (p − различны и отличны от нуля. Значит 1 > r, что противоречит предположению. Сначала докажем, что если требуемое утверждение верно для n = a и для n = b, то оно верно и для n = ab. Пусть дано − 1 целых чисел. Утверждение верно для n = b, а кроме того − 1 > 2b − 1. Поэтому изданных чисел можно выбрать чисел, сумма которых делится на b. Затем из оставшихся чисел, если их не меньше 2b − 1, снова выберем b чисел, сумма которых делится на b. Равенство 2ab − 1 = (2a − 1)b + b − 1 показывает, что так можно поступить 2a − 1 рази получить 2a − 1 наборов по b чисел, причём сумма чисел каждого набора делится нате. среднее арифметическое чисел набора — целое число. Рассмотрим эти средние арифметические. Утверждение верно для n = a, поэтому из − 1 средних арифметических можно выбрать a так, чтобы их сумма делилась на a. В результате получаем a наборов по b чисел. Сумма выбранных ab чисел делится на ab, что и требовалось. Остаётся доказать самую трудную часть задачи требуемое утверждение верно для любого простого числа n = Вместо данных чисел можно рассматривать их остатки отделения на p. Пусть b 1 6 b 2 6 . . . 6 b 2p−1 — остатки отделения данных чисел на p. Рассмотрим ещё p − 1 чисел a 1 = b p +1 − b 2 , a 2 = b p +2 − b 3 , . . . , a p −1 = b 2p−1 − b p . Если a i = 0, то b i = b p +i , а значит b i +1 = . . . = b i +p . В таком случае сумма p чисел b i , b i +1 , делится на p. Остаётся рассмотреть случай, когда все числа a 1 , . . . , отличны от нуля. Пусть x — остаток отделения на p суммы b 1 + b 2 + . . . + Если x = 0, то мы сразу получаем требуемые p чисел. Предположим, что x 6= 0. Согласно задаче 4.51 из чисел a 1 , . . . , можно составить суммы, дающие все различные остатки при делении на p. В частности, можно составить сумму a i 1 + . . . + a i k , дающую остаток p − x. Тогда сумма b 1 + b 2 + . . . + b p + a i 1 + . . . + a i k = b 1 + . . . . . . +b p +(b p +i 1 −b i 1 ) +. . .+(b p +i k −b i k ) делится на p. После очевидных сокращений эта сумма превращается в сумму p данных чисел. Предположим, что n(n + 1) = m k , где m и k — натуральные числа, k > 2. Числа n и n + 1 взаимно простые, поэтому n = и n + 1 = b k , где a и b — натуральные числа. Ясно, что b > a. Но+ 1) k > (a + 1)a k −1 = a k + a k −1 > n + 1. Поэтому b k > (a + 1) k > n + 1. Решения задача) Если |k − l| 6 4 и k 6= l, то наибольший общий делитель чисел k и l не превосходит 4. Поэтому наибольший общий делитель любой пары выбранных чисел не превосходит 4. Из пяти последовательных чисел можно выбрать пару последовательных нечётных чисел. Из двух последовательных нечётных чисел по крайней мере одно не делится на 3. Это число взаимно просто с остальными четырьмя числами. б) Среди данных чисел есть 5 нечётных чисел. Рассмотрим остатки отделения этих пяти чисел на 3, 5 и 7. Среди остатков отделения на 3 нет трёх одинаковых, а среди остатков отделения на 5 и на 7 нет двух одинаковых. Поэтому среди указанных пяти чисел можно выбрать три числа, не делящихся на 3, а среди них выбрать число, не делящееся на 5 и на 7. Это число взаимно просто с остальными девятью числами. Будем считать, что n > m. Подставим x = 2 в тождество 1)(x + 1)(x 2 + 1)(x 4 + 1) . . . (x 2 n−2 + 1) = x 2 n−1 + В результате получим F 1 F 2 . . . F n −1 + 2 = Предположим, что числа и делятся на d. Тогда 2 = = F n − F 1 F 2 . . . тоже делится на d. Но числа и F m нечётные, поэтому d 6= 2. |