Книги по разным темам Pages:     | 1 |   ...   | 16 | 17 | 18 | 19 | 20 |   ...   | 65 |

Пусть x = ky, где k > 1 рациональное число. Тогда (ky)y = (yk)y, поэтому 1 p k-ky = yk, а значит, y = k. Пусть = несократимая дробь. Тогда k - 1 q p p+q q q p + q p + q y = и x =. Числа p и p + q взаимно простые, поэтому p p число y может быть рациональным лишь в том случае, когда p = aq и p + + q = bq для некоторых натуральных a и b. Предположим, что q 2. Тогда aq < p + q aq + qaq-1 < (a + 1)q. Приходим к противоречию, так как между числами aq и (a + 1)q не может находиться число bq = p + q. Поэтому q = 1.

p+1 p 1 Для любого натурального p числа x = 1 + и y = 1 + рациоp p нальны и являются решениями уравнения xy = yx. Эти числа будут целыми лишь при p = 1. В этом случае x = 4 и y = 2.

n n a a 12.17. а) Перепишем уравнение в виде c = +. Будем искать c c решения вида a = a1c и b = b1c, где a1 и b1 натуральные числа. Тогда c = an + bn, a = a1(an + bn) и b = b1(an + bn). Легко проверить, что мы 1 1 1 1 1 действительно получили решение.

б) Выберем натуральные числа p и q так, что pm - qn = 1 (это можно сделать с помощью алгоритма Евклида). Положим c = (an +bn)p, a = a1(an + 1 1 +bn)q и b = b1(an+bn)q, где a1 и b1 произвольные натуральные числа. Тогда 1 1 an + bn = (an + bn)(an + bn)qn = (an + bn)pm = cm.

1 1 1 1 1 12.18. Пусть x+y = a и x2-xy+y2 = b. Тогда ab = n. Число n можно лишь конечным числом способов разложить на множители a и b, поэтому получаем конечное число систем уравнений x + y = a, x2 - xy + y2 = b. Выразим y из первого уравнения и подставим во второе. В результате получим уравнение 150 Глава 12. Уравнения в целых числах x2 -x(a-x)+(a-x)2 = b, которое имеет не более двух решений. Каждому целочисленному решению x этого уравнения соответствует одно целочисленное решение исходной системы, а именно (x, a - x).

12.19. Нетрудно найти одно решение этого уравнения, например, x1 = и y1 = 2. Равенство x2 - 2y1 = 1 можно записать в виде (x1 - y1 2)(x1 + y1 2) = 1.

Ясно, что тогда (x1 - y1 2)n(x1 + y1 2)n = 1.

Кроме того, согласно задаче 6.22 (x1 y1 2)n = xn yn 2. Поэтому x2 - 2yn = 1, n т. е. (xn, yn) тоже решение, причём xn+1 > xn, yn+1 > yn.

12.20. Применим задачу 17.11 для = d. В результате получим, что существует бесконечно много пар взаимно простых чисел x, y, для которых |x - y d| < 1/y. В таком случае |x + y d| < |x - y d| + 2 d|y| < + 2 d y, y а значит, 1 |x2 - dy2| = |x + y d| |x - y d| < + 2 d y 2 d + 1.

y y Таким образом, в качестве константы C можно взять число 2 d + 1.

12.21. Согласно задаче 12.20 для некоторого целого k уравнение x2-dy2 = = k имеет бесконечно много натуральных решений. Выберем два различных 2 решения x2 - dy1 = k и x2 - dy2 = k, для которых y1 y2 (mod k). То1 гда x1 x2 (mod k), поэтому решения можно выбрать так, что x1 x(mod k). В таком случае 2 (x1x2 - dy1y2)2 - d(x1y2 - x2y1)2 = (x2 - dy1)(x2 - dy2) = k1 и x1x2 - dy1y2 x2 - dy1 0 (mod k), x1y2 - x2y1 0 (mod k). При этом x1y2 - x2y1 = 0, поскольку иначе 2 y1 x2 k + dy2 = = = y1 = y2.

2 y2 x2 k + dyПоложим X = k-1(x1x2-dy1y2) и Y = k-1(x1y2-x2y1) = 0. Тогда X2-dY = = 1, т.е. пара X, Y решение уравнения Пелля.

Пусть (x1, y1) фундаментальное решение уравнения Пелля. Тогда (x1 + +y1 d)n(x1-y1 d)n = 1, поэтому пара (xn, yn), где xn+yn d = (x1+y1 d)n, тоже является решением уравнения Пелля, поскольку согласно задаче 6. xn - yn d = (x1 - y1 d)n. Ясно также, что xn - yn d = (x1 + y1 d)-n.

Остаётся проверить, что любое натуральное решение (x, y) представляется в виде x + y d = (x1 + y1 d)n, где n натуральное число. Предположим, Глава 12. Уравнения в целых числах что натуральное решение (x, y) не представляется в таком виде. Тогда можно выбрать натуральное число n так, что (x1 + y1 d)n < x + y d < (x1 + y1 d)n+1.

После умножения на (x1 + y1 d)-n = xn - yn d получим 1 < (x + y d)(xn - yn d) < x1 + y1 d.

Положим (x + y d)(xn - yn d) = X + Y d. Чтобы прийти к противоречию, достаточно показать, что X2 - dY = 1 и X > 0, Y > 0. По усло вию (x + y d)(x - y d) = 1 и (xn - yn d)(xn + yn d) = 1, поэтому (X + + Y d)(X - Y d) = 1, т.е. X2 - dY = 1. Кроме того, X + Y d > 1, а значит, 0 < X - Y d < 1. Следовательно, 2X = (X + Y d) + (X - Y d) > 1 + 0 > 0, 2Y d = (X + Y d) - (X - Y d) > 1 - 1 = 0.

12.22. Ясно, что d имеет простой делитель p = 4k + 3. Предположим, что x2 - dy2 = -1. Тогда x2 -1 (mod p), поэтому число -1 является квадратичным вычетом по модулю p. С другой стороны, если p = 4k + 3 простое число, то согласно задаче 31.36 число -1 не является квадратичным вычетом по модулю p.

12.23. Пусть (x1, y1) фундаментальное решение уравнения Пелля x2-dy2 = 1. Из условия d 1 (mod 4) вытекает, что x2-y1 1 (mod 4). Следовательно, x1 1 (mod 2) и y1 0 (mod 2). Перепишем равенство x2-dy1 = = 1 в виде x1 + 1 x1 - 1 y = d.

2 2 По условию число d простое, поэтому либо x1 + 1 x1 - = da2, = b2, 2 либо x1 + 1 x1 - = a2, = db2.

2 В первом случае получаем b2-da2 = -1. Во втором случае получаем a2-db2 = = 1, что противоречит минимальности решения (x1, y1).

12.24. Положим x + y d x(x2 + 3dy2) y(3x2 + dy2) X + Y d =, т.е. X =, Y =.

2 8 Согласно задаче 4.42 г) x2 1 (mod 8) и y2 1 (mod 8). Следовательно, d2 5 (mod 8), а значит, x2 + 3dy2 1 + 15 0 (mod 8) и 3x2 + dy2 3 + + 5 0 (mod 8), поэтому числа X и Y целые. Кроме того, 3 x + y d x - y d X + Y d = = -1.

2 152 Глава 12. Уравнения в целых числах 12.25. Предположим сначала, что среди чисел n и p есть равные, на m, m пример, n = p. Тогда m2 + 2n2 = 3mn2, т.е. 3m = + 2. Следовательно, n m = dn, где d целое число. При этом d2 + 2 = 3nd, т.е. d(3n - d) = 2. Поэтому d = 1 или 2. В обоих случаях n = 1. В результате получаем решения (1, 1, 1) и (2, 1, 1). Назовём их особыми.

Возьмём теперь неособое решение (m, n, p), для которого числа m, n, p попарно различны, и рассмотрим квадратный трёхчлен f(x) = x2 - 3xnp + n2 + p2.

Ясно, что f(m) = 0, т.е. один корень квадратного трёхчлена f равен m. Второй его корень m можно найти по теореме Виета: m = 3np - m. Ясно, что при этом (m, n, p) решение уравнения (12.1). Покажем, что наибольшее из чисел n и p заключено между m и m. Пусть для определённости n > p. Тогда (n - m)(n - m ) = f(n) = 2n2 + p2 - 3n2p < 0.

Это как раз и означает, что n заключено между m и m.

Аналогичным образом по решению (m, n, p) можно построить решения (m, n, p) и (m, n, p ).

Предположим, что m наибольшее из чисел m, n, p. Тогда m > max(n, p) > m, n < m = max(m, p) < n.

Таким образом, при переходе от решения (m, n, p) к решению (m, n, p) наибольшее из трёх чисел уменьшается, а при переходе к решениям (m, n, p) и (m, n, p ) увеличивается.

Если начинать с решения (1,1,1), то получим следующее дерево решений:

(1, 1, 1) (2, 1, 1) - (5, 2, 1) (13, 1, 5) (29, 5, 2) (34, 1, 13) (194, 13, 5) (433, 5, 29) (169, 29, 2)............

Это дерево содержит все решения, поскольку от произвольного решения после нескольких уменьшений максимума мы перейдём к особому решению. Под уменьшением максимума мы подразумеваем переход от решения (m, n, p), где m > max(n, p), к решению (m, n, p).

12.26. Достаточно доказать, что если m2 + n2 + p2 = mnp, то числа m, n и p делятся на 3. Если целое число не делится на 3, то его квадрат при делении на 3 даёт остаток 1. Поэтому если m2 +n2 +p2 не делится на 3, то среди чисел Глава 12. Уравнения в целых числах m, n и p есть как делящиеся на 3, так и не делящиеся на 3. Но тогда m2 +n2 + + p2 = mnp делится на 3, чего не может быть. Значит, m2 + n2 + p2 делится на 3, причём числа m, n и p одновременно либо все делятся на 3, либо все не делятся на 3. Второй вариант невозможен, потому что mnp = m2 + n2 + pделится на 3.

12.27. Случай k = 2 это задача 12.13 а). Поэтому будем предполагать, что k > 3. Предположим, что x2 + y2 + z2 = k xyz, где x, y, z натуральные числа. Прежде всего покажем, что эти числа попарно различны. Пусть y = z.

Тогда x2 = kxy2 - 2y2 = (kx - 2)y2, поэтому x = y, где натуральное число. При этом 2 = ky - 2, т.е. 2 = (ky - ). Значит, = 1 или 2. В обоих случаях ky = 3, что противоречит неравенству k > 3.

Пусть для определённости x > y > z. Рассмотрим квадратный трёхчлен f(t) = t2 - kyz t + y2 + z2. Один его корень равен x, а второй корень x по теореме Виета равен kyz -x. Ясно, что (y -x)(y -x ) = f(y) = 2y2 +z2 -ky2z < 0, т.е. x > y > x. Таким образом, по решению x, y, z мы построили новое решение x, y, z, для которого x, y, z < x. Повторяя эту конструкцию x раз, приходим к противоречию. (Решающее отличие от уравнения Маркова состоит в том, что здесь нет решения с двумя одинаковыми числами, поэтому операцию уменьшения решения можно применять бесконечно много раз.) 12.28. Предположим, что m = dm1, n = dn1 и p = dp1, где d > 1. Тогда m2 + n2 + p2 = 3d m1n1p1. Но согласно задаче 12.27 уравнение x2 + y2 + z2 = 1 1 = k xyz не имеет решений в натуральных числах при k > 3.

Глава 13.

Индукция 13.1. Вычисление сумм 13.1. Вычислите сумму 1 2 3 n - + + +... +.

2! 3! 4! n! 13.2. Вычислите сумму 1 1! + 2 2! + 3 3! +... + n n!.

m(m + 1) 13.3. Докажите, что 13 + 23 + 33 +... + m3 =.

13.4. Докажите, что 1 1 1 1 1 1 1 - + - +... - = + +... +.

2 3 4 2n n + 1 n + 2 2n 13.2. Неравенства 13.5. Докажите неравенство 1 1! + 2 2! + 3 3! +... + k k! < (k + 1)!.

Глава 13. Индукция 13.6. Докажите, что если 0 < x1,..., xn < 1 и n 2, то (1 - x1)... (1 - xn) > 1 - (x1 +... + xn).

13.7. Докажите, что при целом n 2 и |x| < 2n > (1 - x)n + (1 + x)n.

13.8. Докажите, что 1 1 1 1 + 1 + 1 +... 1 + < 3.

2 4 8 2n 13.9. а) Докажите, что для любого > 0 и любого натурального n > 1 выполняется неравенство (1 + )n > 1 + n.

б) Докажите, что если 0 < 1/n и n натуральное число, то выполняется неравенство (1 + )n < 1 + n + n22.

13.10. Докажите неравенство между средним арифметическим и средним геометрическим для n положительных чисел: (a1a2... an)1/n (a1 +... + an)/n, причём равенство достигается, только если a1 =... = an.

13.11. Докажите, что 3n > n3 для любого натурального n = 3.

13.12. Докажите неравенство n раз 2 - 2 + 2 +... + >.

2 - 2 + 2 +... + n-1 раз 13.3. Доказательство тождеств 13.13. Некоторые из чисел a1, a2,... an равны +1, остальные равны -1. Докажите, что a1a2 a1a2a3 a1a2 ... an 2 sin a1 + + +... + = 2 4 2n-1 = a1 2 + a2 2 + a3 2 +... + an 2.

156 Глава 13. Индукция 13.4. Разные задачи 13.14. На кольцевой автомобильной дороге стоит несколько одинаковых автомобилей. Известно, что если весь бензин, находящийся в автомобилях, слить в один из них, то этот автомобиль сможет проехать по всей кольцевой дороге и вернуться на прежнее место. Докажите, что хотя бы один из этих автомобилей сможет проехать по всей кольцевой дороге в заданном направлении, забирая по пути бензин у остальных автомобилей.

13.15. Докажите, что любую дробь m/n, где 0 < m/n < 1, можно представить в виде m 1 1 1 = + + +... +, n q1 q2 q3 qr где 0 < q1 < q2 <... < qr, причём число qk делится на qk-1 при k = 2, 3,..., r.

См. также задачу 20.11.

Решения 13.1. Докажем индукцией по n, что рассматриваемая сумма равна 1 -.

n! 1 При n = 2 получаем очевидное равенство = 1 -. Предположим, что 2! 2! требуемое равенство доказано для некоторого n. Тогда 1 2 n - 1 n 1 n + +... + + = 1 - + = 2! 3! n! (n + 1)! n! (n + 1)! n + 1 n = 1 - + = 1 -.

(n + 1)! (n + 1)! (n + 1)! 13.2. Докажем индукцией по n, что рассматриваемая сумма равна (n + +1)!-1. При n = 1 получаем очевидное равенство 11! = 2!-1. Предположим, что требуемое равенство доказано для некоторого n. Тогда 1 1! + 2 2! +... + n n! + (n + 1) (n + 1)! = (n + 1)! - 1 + (n + 1) (n + 1)! = = (n + 2)! - 1.

13.3. База индукции очевидна, поэтому нужно лишь проверить равенство m2(m + 1)2 (m + 1)2(m + 2)+ (m + 1)3 =.

4 После деления на m + 1 и умножения на 4 получаем очевидное равенство m2 + 4(m + 1) = (m + 2)2.

Глава 13. Индукция 1 1 1 1 1 1 13.4. Пусть An = 1 - + - +... - и Bn = + +... +.

2 3 4 2n n + 1 n + 2 2n 1 1 1 1 Тогда An+1 = An + - и Bn+1 = Bn - + +.

2n + 1 2n + 2 n + 1 2n + 1 2n + 1 Значит, An+1 -Bn+1 = An -Bn + - = An -Bn. Равенство A1 = Bn + 1 2n + очевидно, поэтому An = Bn для всех n.

13.5. Применим индукцию по k. При k = 1 требуемое неравенство очевидно: 1 1! < 2!. Предположим, что для некоторого k требуемое неравенство выполняется. Тогда 1 1! + 2 2! + 3 3! +... + k k! + (k + 1) (k + 1)! < (k + + 1)! + (k + 1) (k + 1)! = (k + 2)!.

13.6. Применим индукцию по n. Сначала заметим, что (1 - x1)(1 - x2) = 1 - (x1 + x2) + x1x2 > 1 - (x1 + x2). Предположим, что (1 - x1)... (1 - xn-1) > 1 - (x1 +... + xn-1). Тогда (1 - x1)... (1 - xn) > 1 - xn - (x1 +... + xn-1) + xn(x1 +... + xn-1) > 1 - (x1 + +... + xn).

13.7. Применим индукцию по n. При n = 2 получаем (1 - x)2 + (1 + x)2 = = 2(1 + x2) < 4. Предположим теперь, что (1 - x)n + (1 + x)n < 2n. Тогда (1 - x)n+1 + (1 + x)n+1 < ((1 - x)n + (1 + x)n)((1 - x) + (1 + x)) < 2n 2 = 2n+1.

13.8. Требуемое неравенство эквивалентно неравенству 1 1 1 + 1 +... 1 + < 2.

4 8 2n Если 0 < x < 1, то 0 < 1 - x2 < 1, поэтому 1 + x <. Значит, 1 - x -1 1 + < 1 -. Воспользовавшись неравенством из задачи 13.6, по2k 2k лучаем 1 1 1 1 1 1 1 - 1 -... 1 - > 1 - - -... - >.

4 8 2n 4 8 2n 13.9. а) Покажем, что если > 0 и (1 + )n > 1 + n, то (1 + )n+1 > 1 + + (n + 1). Действительно, (1 + )n+1 = (1 + )(1 + )n > (1 + )(1 + n) = = 1 + (n + 1) + n2 > 1 + (n + 1).

б) Для n = 1 требуемое неравенство выполняется. Предположим, что если 0 < 1/n, то выполняется неравенство (1 + )n < 1 + n + n22. Пусть число таково, что 0 < 1/(n+1). Тогда 1/n, поэтому (1+)n+1 < (1+ + n + n22)(1 + ) = 1 + (n + 1) + (n2 + n + n2)2. Остаётся проверить, что n2 + n + n2 (n + 1)2, т.е. n2 n + 1. Это неравенство следует из того, что 1/(n + 1) и n2 < (n + 1)2.

13.10. Докажем сначала требуемое неравенство для чисел вида n = 2m индукцией по m. Для m = 1 оно следует из того, что a - 2 ab + b = = ( a - b)2 0; равенство достигается, только если a = b. Предположим, что требуемое неравенство доказано для m, и докажем его для m + 1. Ясно, m m что akak+2 ((ak + ak+2 )/2)2. Поэтому m+1 m m (a1a2... a2m+1)1/2 (b1b2... b2 )1/2, 158 Глава 13. Индукция m где bk = (ak + ak+2 )/2, а по предположению индукции m 1 m m (b1... b2 )1/2 (b1 +... + b2 ) = (a1 +... + a2m+1).

2m 2m+Пусть теперь n любое. Тогда n < 2m для некоторого m. Положим an+1 = m =... = a2 = (a1 +... + an)/n = A. Ясно, что (a1 +... + an) + (an+1 + m m m +... + a2 ) = nA + (2m - n)A = 2mA и a1... a2 = a1... an A2 -n. Поm m m этому a1... an A2 -n (2mA/2m)2 = A2, т.е. a1... an An; равенство достигается, только если a1 =... = an.

Pages:     | 1 |   ...   | 16 | 17 | 18 | 19 | 20 |   ...   | 65 |    Книги по разным темам