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

б) О т в е т: 119. Пусть n искомое число. Тогда n + 1 делится на НОК(5, 6, 8) = 120. Поэтому n = 119.

4.44. а) О т в е т: 6a + 25b. Пусть 6n 1 (mod 5) и 5m 1 (mod 6). Тогда 6na + 5mb 6na a (mod 5) 6na + 5mb 5mb b (mod 6).

В нашем случае m = 5 и n = 1.

б) О т в е т: 126a + 175b + 120c. Пусть 42k 1 (mod 5), 35n 1 (mod 6) и 30m 1 (mod 7) (здесь 42 = 6 7, 35 = 5 7, 30 = 5 6). Тогда 42ka + 35nb + 30mc 42ka a (mod 5), 42ka + 35nb + 30mc 35nb b (mod 6), 42ka + 35nb + 30mc 30mc c (mod 7).

В нашем случае k = 3, n = 5, m = 4.

4.45. а) Согласно задаче 4.42 б) сумма квадратов двух чисел при делении на 4 может давать остатки 0, 1 и 2.

б) Согласно задаче 4.42 г) сумма квадратов двух чисел при делении на может давать остатки 0, 1, 2, 4 и 5, а сумма квадратов трёх чисел остатки 0, 1, 2, 3, 4, 5 и 6.

4.46. О т в е т: 1946. Пусть N искомое число. По условию N = 131k + + 112 = 132l + 98, где k и l натуральные числа. Кроме того, N < 10 000, N - 98 10 000 - поэтому l = < 75. Далее, 131k + 112 = 132l + 98, поэтому 132 131(k - l) = l - 14. Следовательно, если k = l, то |l - 14| 131. Но l 75, поэтому k = l и l - 14 = 0. Таким образом, N = 131 14 + 112 = 132 14 + 98 = = 1946.

4.47. О т в е т: 523 152 или 523 656.

56 Глава 4. Делимость Полученное число должно делиться на 7 8 9 = 504. Поделим 523 000 на 504 с остатком: 523 000 = 1037 504 + 352. Поскольку 504 - 352 = 152, на делятся числа 523 152 и 523 152 + 504 = 523 656. Других чисел, делящихся на 504, среди чисел от 523 000 до 523 999 нет.

4.48. О т в е т: 5. Заметим, что 106 1 (mod 7), поскольку 103 + 1 делится на 7, и 10k 4 (mod 6) при k 1, поскольку число 99... 96 чётно и делится k на 3. Значит, 1010 104 (mod 7) при k 1. Поэтому требуемый остаток равен остатку от деления числа 10 104 = 105 на 7. Этот остаток равен 5.

4.49. Положим ni = m/mi. Число ni является произведением чисел, взаимно простых с mi, поэтому НОД(ni, mi) = 1. В таком случае можно выбрать целые числа ri и si так, что rimi + sini = 1 (доказательство этого утверждения с помощью алгоритма Евклида приведено на с. 40). Положим ei = sini и x = a1e1 +... + akek. Ясно, что ei 1 (mod mi) и ei 0 (mod mj) при j = i, поэтому x ai (mod mi), i = 1,..., k.

Если x1 и x2 решения рассматриваемой системы сравнений, то x1 - x2 0 (mod mi), i = 1,..., k. Числа m1,..., mk попарно взаимно простые, поэтому x1 - x2 делится на m.

4.50. Ясно, что 23 = 8 1 (mod 7). Поэтому 23k 1 (mod 7), 23k+1 (mod 7) и 23k+2 4 (mod 7). Следовательно, 2n - 1 делится на 7 тогда и только тогда, когда n делится на 3.

4.51. Применим индукцию по r. При r = 1 есть две суммы: 0 и a1. Предположим, что утверждение верно для r < p - 1 чисел и неверно для r + 1 чисел.

Тогда суммы 0, s1,..., sr, составленные из чисел a1,..., ar, дают разные остатки при делении на p, но все суммы 0 + ar+1, s1 + ar+1,..., sr + ar+1 при делении на p не дают новых остатков по сравнению с 0, s1,..., sr. Значит, ar+1 si (mod p) для некоторого i. Далее, si + ar+1 sj (mod p) для некоторого j, т.е. 2ar+1 sj (mod p). Аналогично получаем, что остатки от деления на p чисел ar+1, 2ar+1, 3ar+1,..., (p - 1)ar+1 содержатся среди остатков от деления на p чисел 0, s1,..., sr. Число p простое, и ar+1 не делится на p.

Поэтому остатки от деления на p чисел ar+1, 2ar+1,..., (p - 1)ar+1 различны и отличны от нуля. Значит, p - 1 r, что противоречит предположению.

4.52. Сначала докажем, что если требуемое утверждение верно для n = a и для n = b, то оно верно и для n = ab. Пусть дано 2ab - 1 целых чисел.

Утверждение верно для n = b, а кроме того, 2ab - 1 2b - 1. Поэтому из данных 2ab - 1 чисел можно выбрать b чисел, сумма которых делится на b.

Затем из оставшихся чисел, если их не меньше 2b - 1, снова выберем b чисел, сумма которых делится на b. Равенство 2ab - 1 = (2a - 1)b + b - 1 показывает что так можно поступить 2a - 1 раз и получить 2a - 1 наборов по b чисел, причём сумма чисел каждого набора делится на b, т.е. среднее арифметическое чисел набора целое число. Рассмотрим эти средние арифметические.

Утверждение верно для n = a, поэтому из 2a - 1 средних арифметических можно выбрать a так, чтобы их сумма делилась на a. В результате получаем a наборов по b чисел. Сумма выбранных ab чисел делится на ab, что и Глава 4. Делимость требовалось.

Остаётся доказать самую трудную часть задачи: требуемое утверждение верно для любого простого числа n = p.

Вместо данных чисел можно рассматривать их остатки от деления на p. Пусть b1 b2... b2p-1 остатки от деления данных чисел на p.

Рассмотрим ещё p-1 чисел a1 = bp+1 -b2, a2 = bp+2 -b3,..., ap-1 = b2p-1 -bp.

Если ai = 0, то bi = bp+i, а значит, bi = bi+1 =... = bi+p. В таком случае сумма p чисел bi, bi+1, bi+p делится на p. Остаётся рассмотреть случай, когда все числа a1,..., ap-1 отличны от нуля.

Пусть x остаток от деления на p суммы b1 + b2 +... + bp. Если x = = 0, то мы сразу получаем требуемые p чисел. Предположим, что x = 0.

Согласно задаче 4.51 из чисел a1,..., ap-1 можно составить суммы, дающие все различные остатки при делении на p. В частности, можно составить сумму ai1 +... + aik, дающую остаток p - x. Тогда сумма b1 + b2 +... + bp + ai1 + +... + aik = b1 +... + bp + (bp+i1 - bi1) +... + (bp+ik - bik) делится на p. После очевидных сокращений эта сумма превращается в сумму p данных чисел.

4.53. Предположим, что n(n + 1) = mk, где m и k натуральные числа, k 2. Числа n и n + 1 взаимно простые, поэтому n = ak и n + 1 = bk, где a и b натуральные числа. Ясно, что b > a. Но (a + 1)k > (a + 1)ak-1 = ak + + ak-1 n + 1. Поэтому bk (a + 1)k > n + 1.

4.54. а) Если |k - l| 4 и k = l, то наибольший общий делитель чисел k и l не превосходит 4. Поэтому наибольший общий делитель любой пары выбранных чисел не превосходит 4. Из пяти последовательных чисел можно выбрать пару последовательных нечётных чисел. Из двух последовательных нечётных чисел по крайней мере одно не делится на 3. Это число взаимно просто с остальными четырьмя числами.

б) Среди данных чисел есть 5 нечётных чисел. Рассмотрим остатки от деления этих пяти чисел на 3, 5 и 7. Среди остатков от деления на 3 нет трёх одинаковых, а среди остатков от деления на 5 и на 7 нет двух одинаковых. Поэтому среди указанных пяти чисел можно выбрать три числа, не делящихся на 3, а среди них выбрать число, не делящееся на 5 и на 7. Это число взаимно просто с остальными девятью числами.

4.55. Будем считать, что n > m. Подставим x = 2 в тождество n-2 n-(x - 1)(x + 1)(x2 + 1)(x4 + 1)... (x2 + 1) = x2 + 1.

В результате получим F1F2... Fn-1 + 2 = Fn.

Предположим, что числа Fn и Fm делятся на d. Тогда 2 = = Fn - F1F2... Fn-1 тоже делится на d. Но числа Fn и Fm нечётные, поэтому d = 2.

4.56. Посмотрим, какие остатки может давать простое число p > 3 при делении на 6. Оно не может давать остаток 2 или 4, поскольку иначе оно было бы чётно. Оно не может давать остаток 3, поскольку иначе оно делилось бы на 3. Значит, простое число p > 3 при делении на 6 даёт остаток 1 или 5, т.е.

оно имеет вид 6n 1; его квадрат имеет вид 36n2 12n + 1.

58 Глава 4. Делимость 4.57. Предположим, что существует лишь конечное число различных простых чисел, а именно, p1,..., pr. Рассмотрим число p1... pr + 1. Оно не делится ни на одно из чисел p1,..., pr, поэтому у него есть простой делитель, отличный от p1,..., pr.

4.58. Предположим, что p1,..., pr все различные простые числа вида 4k - 1. Рассмотрим число 4p1... pr - 1. Оно нечётно, поэтому все его простые делители имеют вид 4k 1. Ясно также, что все простые делители не могут иметь вид 4k + 1, поскольку произведение чисел такого вида имеет такой же вид. Остаётся заметить, что рассматриваемое число не делится на p1,..., pr.

4.59. а) Многочлен xq - 1 делится на x - 1, поэтому 2pq - 1 = (2p)q - делится на 2q - 1.

б) Если q нечётно, то многочлен xq + 1 делится на x + 1. Поэтому если число n имеет нечётный делитель q > 1, то 2n + 1 делится на 2q + 1.

4.60. Воспользуемся тождеством x4+x2+1 = (x2+1-x)(x2+1+x). При x = n-= 22 получаем, что рассматриваемое число является произведением чисел n-1 n-2 n-1 n-22 + 22 + 1 и 22 - 22 + 1. Эти числа взаимно просты, поскольку n-они нечётны, а их разность равна 22 +1. Теперь можно воспользоваться n-1 n-индукцией по n, поскольку число 22 + 22 + 1 имеет тот же самый вид.

4.61. Пусть a = a1 + a2n и b = b1 + b2n. Тогда a b = a1 b1 + (a2 b2)n и ab = a1b1 + (a2b1 + a1b2 + a2b2n)n.

4.62. Если xa ya (mod p), то (x - y)a делится на p. Числа a и p взаимно простые, поэтому x - y делится на p. Значит, если 1 x, y p - 1, то x = y.

4.63. Согласно задаче 4.62 ровно один из остатков от деления на p чисел b, 2b,..., (p - 1)b равен 1. Значит, существует единственное целое число b, 1 b p - 1, для которого bb 1 (mod p). При этом a b(ab) (mod p).

Глава 5.

Тождества 5.1. Разложения на множители В задачах 5.1Ц5.8 требуется разложить указанные выражения хотя бы на два множителя меньшей степени, не используя радикалов.

5.1. а) xn - yn; б) x2n+1 + y2n+1.

5.2. x4 + 4.

5.3. (x + y + z)3 - x3 - y3 - z3.

5.4. x3 + y3 + z3 - 3xyz.

5.5. (x - y)3 + (y - z)3 + (z - x)3.

5.6. a10 + a5 + 1.

5.7. a4(b - c) + b4(c - a) + c4(a - b).

5.8. x4 + x3 + x2 + x + 12.

* * * 5.9. а) Разложите x8 + x4 + 1 на два множителя.

б) Разложите x8 + x4 + 1 на четыре множителя, допуская в качестве коэффициентов квадратные корни из натуральных чисел.

5.2. Доказательство тождеств 5.10. Докажите, что для любого натурального n справедливо соотношение (2n)! = 2n (2n - 1)!! n! 60 Глава 5. Тождества 5.3. Суммы квадратов 5.11. Докажите, что если каждое из чисел m и n представимо в виде суммы двух квадратов целых чисел, то их произведение mn тоже представимо в виде суммы квадратов двух целых чисел.

5.12. а) Представьте в виде суммы квадратов (a2 + a2 + a2)(b2 + b2 + b2) - (a1b1 + a2b2 + a3b3)2.

1 2 3 1 2 б) Представьте в виде суммы квадратов (a2 +... + a2 )(b2 +... + b2 ) - (a1b1 +... + anbn)1 n 1 n (тождество Лагранжа).

5.4. Вспомогательные тождества 5.13. Известно, что число a+1/a целое. а) Докажите, что число a2 + + 1/a2 тоже целое. б) Докажите, что число an + 1/an целое для любого натурального n.

5.14. Докажите, что любое нечётное число есть разность двух квадратов целых чисел.

5.15. Докажите, что произведение четырёх последовательных целых чисел в сумме с единицей даёт полный квадрат.

1 1 1 1 1 1 5.16. Докажите, что если + + = то + + = a b c a + b + c an bn cn = для любого нечётного n.

an + bn + cn 5.17. Пусть x, y, z попарно различные целые числа. Докажите, что число (x - y)5 + (y - z)5 + (z - x)5 делится на 5(y - z)(z - x)(x - y).

a b c a 5.18. Докажите, что если + + = 0, то + b - c c - a a - b (b - c)b c + + = 0.

(c - a)2 (a - b)5.19. Докажите, что n2 + 3n + 5 ни при каком целом n не делится на 121.

5.20. Докажите, что выражение x5 + 3x4y - 5x3y2 - 15x2y3 + 4xy4 + 12yГлава 5. Тождества не равно 33 ни при каких целых значениях x и y.

5.21. Докажите, что для любого натурального n 2 число 24n+2 + не является произведением двух простых чисел.

5.22. Докажите, что любое рациональное число можно представить в виде суммы трёх кубов рациональных чисел.

5.5. Разложения рациональных функций 2 2x a 5.23. Представьте дроби и в виде суммы дробей + x2 - 1 x2 - 1 x - b +, где a и b действительные числа.

x + 5.24. Пусть числа a1,..., an попарно различны. Докажите, что можно выбрать числа A1,..., An так, что 1 A1 An = +... +.

(x + a1) ... (x + an) x + a1 x + an 5.25. Пусть a1 < a2 < a3 <... < an и 1 A1 A2 An = + +... +, (x + a1)(x + a2)... (x + an) x + a1 x + a2 x + an где A1,..., An действительные числа. Докажите, что A1 > 0, A2 < 0, A3 > 0,...

5.6. Разложения квадратичных функций 5.26. Докажите, что если для всех x, y, z справедливо равенство a11x2 + a22y2 + a33z2 + 2a12xy + 2a13xz + 2a23yz = = (b1x + b2y + b3z)(c1x + c2y + c3z), то a11a22a33 + 2a13a12a23 = a2 a11 + a2 a22 + a2 a33.

23 13 5.7. Тождества с целыми частями 5.27. Докажите, что 1 2 n - [x] + x + + x + +... + x + = [nx].

n n n 62 Глава 5. Тождества 5.28. Пусть p и q взаимно простые натуральные числа. Докажите, что q 2q (p - 1)q (p - 1)(q - 1) + +... + =.

p p p 5.29. Пусть p и q взаимно простые нечётные натуральные числа.

Докажите, что p - 1 q - q p q 2q (p - 1)(q - 1) + p + 2p +...+ + +...+ 2 =.

p p p q q q (Эйзенштейн) 5.30. Докажите, что [ n + n + 1] = [ 4n + 2] для любого натурального числа n.

5.31. Докажите, что [ n + n + 1 + n + 2] = [ 9n + 8] для любого натурального числа n.

3 5.32. Докажите, что [ n + n + 1] = [ 8n + 3] для любого натурального числа n.

Решения 5.1. а) (x - y)(xn-1 + xn-2y +... + yn-1).

б) (x + y)(x2n - x2n-1y + x2n-2y2 -... + y2n).

5.2. (x2 - 2x + 2)(x2 + 2x + 2).

5.3. 3(x + y)(y + z)(z + x).

5.4. (x + y + z)(x2 + y2 + z2 - xy - yz - zx).

5.5. 3(x - y)(y - z)(z - x).

5.6. (a2 + a + 1)(a8 - a7 + a5 - a4 + a3 - a + 1).

5.7. (a2 + b2 + c2 + ab + bc + ca)(a - b)(b - c)(a - c).

5.8. (x2 - 2x + 3)(x2 + 3x + 4).

5.9. а) (x4 + x2 + 1)(x4 - x2 + 1).

б) Каждый из полученных многочленов четвёртой степени можно разложить на множители, воспользовавшись тождеством (x2 + ax + 1)(x2 - ax + 1) = x4 + (2 - a2)x2 + 1;

нужно положить a = 1 и a = 3.

5.10. Ясно, что n!2n = 2 4 6 ... 2n. Поэтому n!2n(2n - 1)!! = = (2 4 6 ... 2n)1 3 5 ... (2n - 1) = (2n)!.

Глава 5. Тождества 5.11. Воспользуйтесь тождеством (a2 +b2)(c2 +d2) = (ac+bd)2 +(ad-bc)2.

5.12. а) (a1b2 - a2b1)2 + (a2b3 - a3b2)2 + (a1b3 - a3b1)2.

б) (aibj - ajbi)2, где суммирование ведётся по всем парам i < j.

1 5.13. а) Воспользуйтесь тождеством a2 + = a + - 2.

a2 a б) Воспользуйтесь тождеством 1 1 1 an+1 + = an + a + - an-1 +.

an+1 an a an-5.14. Воспользуйтесь тождеством 2n + 1 = (n + 1)2 - n2.

5.15. Достаточно заметить, что n(n + 1)(n + 2)(n + 3) + 1 = n(n + 3) + 1.

1 1 1 5.16. Равенство + + = эквивалентно равенству (bc + ca + a b c a + b + c + ab)(a + b + c) = abc, т.е. (a + b)(b + c)(c + a) = 0 (предполагается, что abc = и a + b + c = 0). Таким образом, тройка чисел a, b, c имеет вид x, -x, y, причём y = x. Но тогда тройка чисел an, bn, cn при нечётном n тоже имеет такой вид.

5.17. Несложно проверить, что частное равно x2 + y2 + z2 - xy - yz - xz.

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