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

В конце концов получим p1 = qi. После этого доказательство завершается очевидной индукцией.

4.10. Найдём наибольший общий делитель чисел 21n + 4 и 14n + 3, пользуясь алгоритмом Евклида. Поделив 21n + 4 на 14n + 3, получим в остатке 7n + 1. Поделив 14n + 3 на 7n + 1, получим в остатке 1. Значит, числа 21n + и 14n + 3 взаимно простые.

4.11. Для любой пары натуральных чисел {m, n}, где m > n, последовательные операции {m, n} {m - n, n} приводят к паре {d, d}, где d = = НОД(m, n). Действительно, операция деления m на n с остатком состоит из нескольких таких операций.

4.12. Согласно задаче 4.11 достаточно проверить, что НОД(am - 1, an - 1) = НОД(am-n - 1, an - 1) для любых m > n 1.

Но am - 1 = an(am-n - 1) + an - 1 и числа a и an - 1 взаимно простые.

48 Глава 4. Делимость b b 4.13. Пусть p = pa1... pam, q = q11... qnn. Тогда f(p/q) = m 2b1-1 2bn-= p2a1... p2amq1... qn. Ясно, что каждое натуральное число предстаm вимо в таком виде ровно одним способом.

4.14. а) Число 10 при делении на 3 даёт остаток 1. Поэтому 10k при делении на 3 тоже даёт остаток 1. Следовательно, ak10k при делении на даёт остаток ak.

б) Решение аналогично решению задачи а).

в) Число 10 при делении на 11 даёт остаток -1. Поэтому 10k при делении на 11 даёт остаток (-1)k. Следовательно, ak10k при делении на 11 даёт остаток (-1)kak.

4.15. Это число делится на 3, но не делится на 9, поэтому оно не может быть полным квадратом.

4.16. Пусть a и b семизначные числа, составленные посредством этих жетонов. Предположим, что a делится на b и a = b. Тогда a - b тоже делится a - b на b. Ясно, что 7. С другой стороны, a - b делится на 9, а b не делится b a - b на 9. Поэтому делится на 9. Приходим к противоречию.

b 4.17. Мы заменяем число 10a + b на a + 2b. Для любого числа 10a + b, большего 19, имеет место неравенство 9a > b, т.е. 10a + b > a + 2b. Поэтому при указанных преобразованиях число всегда уменьшается. Ясно, что 10a + b делится на 19 тогда и только тогда, когда 20a + 2b делится на 19, т.е. a + 2b делится на 19.

4.18. Запишем исходное число в виде 10a + a0. Нужно доказать, что оно делится на 7 тогда и только тогда, когда a - 2a0 делится на 7. Ясно, что 10a + +a0 делится на 7 тогда и только тогда, когда 20a+2a0 делится на 7. Остаётся заметить, что при делении на 7 число 20a + 2a0 даёт такой же остаток, как и число -a + 2a0.

4.19. а) Пусть a = p1... pk и b = p1... pk. Тогда 1 k 1 k НОД(a, b) = pmin{1,1}... pmin{k,k}, 1 k НОК(a, b) = pmax{1,1}... pmax{k,k}.

1 k Поэтому доказательство можно провести для каждого простого множителя отдельно.

ab Если a = p и b = p, причём, то НОД(a, b) = p и = НОК(a, b) pp = = p.

p б) Достаточно рассмотреть случай, когда a = p, b = p, c = p, причём. В этом случае НОД(a, b, c) = p, abc НОК(a, b, c) pppp = = p.

НОК(a, b) НОК(b, c) НОК(c, a) ppp Глава 4. Делимость в) Достаточно заметить, что pppp = p.

ppp 4.20. Пусть наибольшая степень простого числа p, на которую делятся a, b, c, равна,,. Требуется доказать, что min(, min(, )) = = min(min(, ), )) = min(,, ), где min(x, y) наименьшее из чисел x и y. Это утверждение о наименьших числах очевидно.

4.21. Согласно задаче 4.19 а) (a + b)ab (a + b)ab (a + b) НОК(a, b) = = = НОД(a, b) НОД(a, a + b) = b НОК(a, a + b).

4.22. Предположим, что числа a + b и a2 + b2 делятся на d. Тогда число 2ab = (a+b)2 -(a2 +b2) тоже делится на d. Поэтому числа 2a2 = 2a(a+b)-2ab и 2b2 = 2b(a + b) - 2ab тоже делятся на d. По условию числа a и b взаимно просты, поэтому числа a2 и b2 тоже взаимно просты. Значит, d = 1 или 2.

4.23. В наименьшее общее кратное чисел a и b входят только те простые делители, которые входят в a и b. Только они и могут входить в наибольший общий делитель суммы и наименьшего общего кратного. Поэтому достаточно проследить за степенью каждого простого множителя отдельно. Пусть a = = p... и b = p..., причём. Тогда сумма чисел a и b имеет вид p..., а их наименьшее общее кратное имеет вид p.... Поэтому рассматриваемый наибольший общий делитель имеет вид p.... Наибольший общий делитель самих чисел a и b имеет такой же вид.

4.24. Пусть наименьшее общее кратное данных чисел равно a. Тогда a a a a > >... > различные натуральные числа. Поэтому n, a1 a2 an aт.е. a na1.

4.25. Функция f(a, b) = НОК(a, b) обладает свойствами (1)Ц(3); свойства (1) и (2) очевидны, а свойство (3) доказано в задаче 4.21. Легко видеть, что свойства (2) и (3) позволяют вычислить f(a, b), если известны значения f(a1, b1) для всех натуральных a1 и b1, для которых a1 + b1 < a + b. Поэтому функция f(a, b) единственна.

4.26. Пусть a1,..., an данные числа. Количество членов ряда 1, 2, 3, N..., N, делящихся на ak, равно. По условию наименьшее общее кратное ak любых двух из чисел a1,..., an больше N, поэтому среди чисел 1, 2,..., N нет ни одного числа, делящегося одновременно на два из чисел a1,..., an.

Поэтому число членов последовательности 1, 2,..., N, делящихся хотя бы на одно из чисел a1,..., an, равно N N N + +... +.

a1 a2 an 50 Глава 4. Делимость Но в последовательности 1, 2,..., N всего N членов, поэтому N N N + +... + N.

a1 a2 an N N Учитывая, что > - 1, получаем ak ak N N N - 1 + - 1 +... + - 1 < N, a1 a2 an т.е.

N N N N + + +... + < N + n < 2 N.

a1 a2 a3 an Сокращая обе части на N, получаем требуемое.

4.27. Число an - bn делится на a - b (задача 5.1 а), поэтому 72n - 52n делится на 72 - 52 = 24.

4.28. Нужно доказать, что 3n5 + 5n3 + 7n делится на 15, т.е. 5n3 + 7n делится на 3 и 3n5 + 7n делится на 5. Ясно, что 5n3 + 7n -(n3 - n) (mod 3) и 3n5 + 7n -2(n5 - n) (mod 5). Рассматривая все различные остатки, легко проверить, что n3 - n делится на 3, а n5 - n делится на 5.

4.29. О т в е т: при чётных n. Прежде всего заметим, что 323 = 17 19, поэтому число делится на 323 тогда и только тогда, когда оно делится на и на 19. Число 20n - 3n делится на 20 - 3 = 17. Далее, 16n (-1)n (mod 17), поэтому число 16n - 1 делится на 17 тогда и только тогда, когда n чётно. Что касается делимости на 19, то 20n - 1 делится на 20 - 1 = 19 при любом n, а при n = 2m число 16n - 3n делится на 162 - 32 = 13 19, поэтому оно делится на 19.

4.30. Многочлен xn - yn делится на x - y (задача 5.1 а), поэтому bn - kn делится на b - k. Значит, число a - bn = (a - kn) - (bn - kn) делится на b - k при любом k = b. Это возможно лишь в том случае, когда a = bn.

4.31. Пусть 2n - 2 = nm. Тогда n n 22 -1 - 2 22 -2 - 1 2nm - = 2 = 2 = 2n - 1 2n - 1 2n - = 2(2n(m-1) + 2n(m-2) +... + 2n + 1).

4.32. Если m = kn, где k нечётное число, то am + bm = (an)k + (bn)k делится на an + bn (задача 5.1 б).

Пусть m = kn + r, где k нечётное число и 0 < r < n. Докажем, что am + bm не делится на an + bn. Действительно, akn+r + bkn+r = ar(akn + bkn) + bkn(br - ar).

Здесь ar(akn + bkn) делится на an + bn, а bkn(br - ar) не делится на an + bn, поскольку bkn взаимно просто с an + bn и 0 < |br - ar| < an + bn.

Глава 4. Делимость Пусть m = ln + r, где l чётное число и 0 r < n. Докажем, что am + bm не делится на an + bn. Действительно, пусть k = l - 1 (k нечётное число).

Тогда aln+r + bln+r = aknan+r + bknbn+r = = an+r(akn + bkn) + bkn+r(an + bn) - bknan(ar + br).

Здесь первые два слагаемых делятся на an + bn, а последнее не делится, поскольку bknan взаимно просто с an + bn и 0 < ar + br < an + bn.

4.33. Решим сразу задачу б). Предположим, что рассматриваемое число целое. Выберем среди чисел k, k + 1,..., k + n те, которые делятся на наибольшую степень двойки. Пусть такое число только одно, именно, 2mp, где а 1 1 2q r + 2q p нечётно. Тогда рассматриваемое число имеет вид + =, 2m p r 2mpr где числа p и r нечётные. Это число представляет собой дробь с нечётным знаменателем и чётным числителем; такое число не может быть целым.

Поэтому есть по крайней мере два числа, которые делятся на максимальную степень двойки, а именно, 2mp и 2mq, где p < q и p, q нечётные числа.

Но тогда p+1 < q и p+1 чётное число. Поэтому число 2m(p+1) содержится среди чисел k, k + 1,..., k + n и делится на 2m+1, что противоречит выбору числа m.

4.34. Рассмотрим общее выражение (akm+bkn)!dk, где ak и bk целые k неотрицательные числа, dk целые числа.

Наивысшая степень простого чис ла p, на которую делится число n!, равна [n/pm] (задача 4.36). Поэтому m= если для любых чисел x, y 0 выполняется неравенство dk[akx + bky] 0, то рассматриваемое выражение является целым числом.

В задачах а) - г) числа ak, bk, dk связаны соотношением dkak = k = dkbk = 0. В таком случае функция f(x, y) = dk(akx + bky) обладает k k следующим свойством: f(x+1, y) = f(x, y) = f(x, y +1). Поэтому неравенство f(x, y) 0 достаточно проверить для чисел x, y, удовлетворяющих неравенствам 0 x, y < 1.

а) Нужно доказать неравенство [x + y] - [x] - [y] 0 для 0 x, y < 1. Но [x] = [y] = 0.

б) Нужно доказать неравенство [2x] + [2y] - [x] - [y] - [x + y] 0 для 0 x, y < 1. Учитывая, что [x] = [y] = 0, переходим к неравенству f(x, y) = = [2x] + [2y] - [x + y] 0. Чтобы вычислить значение функции f(x, y) в квадрате 0 x, y < 1, поступим следующим образом. Нарисуем графики 2x = 1 и 2y = 1 сплошными линиями, а график x + y = 1 пунктирной линией (рис. 4.1).

Ясно, что f(0, 0) = 0; поэтому f = 0 и во всех точках фигуры, ограниченной этими графиками и сторонами квадрата и содержащей начало координат.

При переходе через сплошную линию значение функции f увеличивается на 1, а при переходе через пунктирную линию уменьшается на 1 (имеется в виду движение в направлении от начала координат). Это замечание позволя52 Глава 4. Делимость Рис. 4.1. Графики в квадрате (б) ет вычислить значение функции f(x, y) во всех точках квадрата и убедиться, что они неотрицательны. На рис. 4.1 эти значения выписаны.

в) Нужно доказать неравенство f(x, y) = [5x] + [5y] - [3x + y] - [x + 3y] для 0 x, y < 1. Чтобы вычислить значение функции f(x, y) во всех точках квадрата, для каждого выражения [akx+bky] нарисуем графики akx+bky = = 1, 2,..., ak +bk -1; для знака плюс график рисуем сплошной линией, а для знака минус пунктирной (рис. 4.2). Затем пользуемся теми же правилами, что и при решении задачи б).

г) Нужно доказать неравенство f(x, y) = [3x + 3y] + [3y] + [2x] + [2y] - [2x + +3y]-[x+2y]-[x+y] 0. Это делается так же, как и при решении задачи в):

см. рис. 4.3. Отметим, что график x + y = 1 мы не рисуем, потому что при прохождении через этот график значение функции f(x, y) увеличивается на 1 и уменьшается на 1, т.е. не изменяется.

4.35. О т в е т: 24. Среди чисел от 1 до 100 есть 20 чисел, делящихся на 5, а среди чисел, делящихся на 5, есть 4 числа, делящихся на 25 (чисел, делящихся на 125, среди данных чисел нет). Поэтому рассматриваемое произведение делится на 524 и не делится на 525. Ясно также, что оно делится на 224.

n n 4.36. Среди чисел 1, 2,..., n есть чисел, делящихся на p, чисел, p pделящихся на p2, и т.д.

4.37. Пусть a наибольшее целое число, для которого n! делится на 2a.

Согласно задаче 4. n n n n n n a = + + +... + + +... = n, 2 22 23 2 22 n n поскольку [x] x. Кроме того, = 0 < при достаточно больших k.

2k 2k Поэтому a < n.

Глава 4. Делимость Рис. 4.2. Графики в квадрате (в) Рис. 4.3. Графики в квадрате (г) 54 Глава 4. Делимость 4.38. Пусть (2n - 1)!! = 1 3 5 7... (2n - 1) и (2n)!! = 2 4 6... 2n. Ясно, что (2n)! = (2n - 1)!!(2n)!! и (2n)!! = 2nn!. Поэтому (n + 1)(n + 2)... 2n = (2n)! (2n - 1)!!(2n)!! = = = 2n(2n - 1)!!, причём число (2n - 1)!! нечётно.

n! n! 4.39. О т в е т: 1 и 4. При n > 1 должны выполняться равенства 2k5l = n и 2s5t = n + 1. Числа n и n + 1 взаимно простые, поэтому должно выполняться либо равенство 2k + 1 = 5t, либо равенство 5l + 1 = 2s. Предположим, что 5l + 1 = 2s. Тогда число 2s оканчивается на 6, поэтому s = 4m. Значит, 5l = = 24m-1 = (22m-1)(22m+1). Но числа 22m-1 и 22m+1 не могут одновременно делиться на 5.

Рассмотрим теперь уравнение 2k + 1 = 5t. Пусть t = 2ms, где s нечётно.

Тогда m m m 5t - 1 = (52 - 1)(52 (s-1) + 52 (s-2) +... + 1).

Второй множитель состоит из нечётного числа нечётных слагаемых, т.е. он нечётен. Значит, s = 1. Далее, m m-52 - 1 = (5 - 1)(5 + 1)(52 + 1)... (52 + 1).

Число 5 + 1 = 6 не является степенью двойки, поэтому m = 0. Это соответствует равенству 22 + 1 = 5.

4.40. а) Пусть k = 2n. Тогда n-1 n-1 n-ak -1 = (a2 -1)(a2 +1) = (a-1)(a+1)(a2 +1)(a4 +1)... (a2 +1). (1) Число a нечётно, поэтому в этом произведении есть n + 1 чётных сомножителей. Значит, ak - 1 делится на 2n+1. Таким образом, если k = 2n и n m - 1, то ak - 1 делится на 2m.

б) Введём следующее обозначение: если m = 2ns, где число s нечётно, то n n n d(m) = n. Ясно, что am - 1 = (a2 - 1)(a2 (s-1) + a2 (s-2) +... + 1), где сумма во второй скобке состоит из нечётного числа нечётных слагаемых. Поэтому n n-d(am - 1) = d(a2 - 1). Далее, в разложении (1) числа a2 + 1,..., a2 + + 1 делятся на 2 и не делятся на 4, поскольку квадрат нечётного числа даёт остаток 1 при делении на 4. Значит, n d(a - 1) при n = 0;

d(a2 - 1) = d(a2 - 1) + n - 1 при n 1.

Число am - 1 делится на 2m тогда и только тогда, когда d(am - 1) m.

Разберём два случая. Если d(m) = 0, т.е. число m нечётно, то должно выполняться неравенство m d(a - 1). Это неравенство имеет конечное число нечётных решений. Если d(m) 1, т.е. число m чётно, то должно выполняться неравенство d(a2 - 1) + n - 1 m = 2ns, где n = d(m). Это неравенство d(a2 - 1) + n - можно переписать в виде s (число s нечётно). Такое нера2n венство имеет конечное число решений, поскольку последовательность n/2n стремится к нулю при n (задача 25.18).

Глава 4. Делимость 4.41. а) О т в е т: 1, 2 и 4. Воспользуемся решением задачи 4.40 б). Если 2 + n a = 3, то d(a - 1) = 1 и d(a2 - 1) = 3. Неравенство s имеет следующие 2n решения: (s, n) = (1, 1) и (1, 2).

б) О т в е т: 1, 2, 4, 6 и 8. Если a = 31, то d(a-1) = 1 и d(a2-1) = d(3032) = 5 + n = 6. Неравенство s имеет следующие решения: (s, n) = (1, 1), (3, 1), 2n (1, 2) и (1, 3). (Напомним, что число s нечётно.) 4.42. а) О т в е т: 0 и 1. Воспользуйтесь равенством (3k 1)2 = 9k2 6k +1.

б) О т в е т: 0 и 1. Воспользуйтесь равенством (2k + 1)2 = 4k2 + 4k + 1.

в) О т в е т: 0, 1 и 4. Воспользуйтесь равенствами (5k 1)2 = 25k2 10k + и (5k 2)2 = 25k2 20k + 4.

г) О т в е т: 0, 1 и 4. Воспользуйтесь равенствами (2k + 1)2 = 4k(k + 1) + и (4k + 2)2 = 16k2 + 16k + 4 и заметьте, что число k(k + 1) чётно.

4.43. а) О т в е т: 209. Пусть n искомое число. Тогда n + 1 делится на 5 6 7 = 210. Поэтому n = 209.

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