Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
12.21. Согласно задаче 12.20 для некоторого целого k уравнение имеет бесконечно много натуральных решений. Выберем два различных решения x 2 1 − dy 2 1 = k и x 2 2 − dy 2 2 = k, для которых y 1 ≡ y 2 (mod k). Тогда x 1 ≡ ±x 2 (mod k), поэтому решения можно выбрать так, что x 1 ≡ x 2 (mod k). В таком случае dy 1 y 2 ) 2 − d(x 1 y 2 − x 2 y 1 ) 2 = (x 2 1 − dy 2 1 )(x 2 2 − dy 2 2 ) = и x 1 x 2 − dy 1 y 2 ≡ x 2 1 − dy 2 1 ≡ 0 (mod k), x 1 y 2 − x 2 y 1 ≡ 0 (mod k). При этом x 1 y 2 − x 2 y 1 6= 0, поскольку иначе 1 y 2 2 = x 2 1 x 2 2 = k + dy 2 1 k + dy 2 2 =⇒ y 2 1 = y 2 Положим X = k −1 (x 1 x 2 − dy 1 y 2 ) и Y = k −1 (x 1 y 2 − x 2 y 1 ) 6= 0. Тогда dY 2 = 1, те. пара (X, Y) — решение уравнения Пелля. Пусть (x 1 , y 1 ) — фундаментальное решение уравнения Пелля. Тогда (x 1 + y 1 √ d) n (x 1 − y 1 √ d) n = 1, поэтому пара (x n , y n ), где+ y n √ d = (x 1 + y 1 √ d) n , тоже является решением уравнения Пел- ля, поскольку согласно задаче 6.22 x n − y n √ d = (x 1 − y 1 √ d) n . Ясно также, что x n − y n √ d = (x 1 + y 1 √ d) −n . Остаётся проверить, что любое натуральное решение (x, y) представляется в виде x + y √ d = = (x 1 + y 1 √ d) n , где n — натуральное число. Предположим, что натуральное решение (x, y) не представляется в таком виде. Тогда можно выбрать натуральное число n так, что+ y 1 √ d) n < x + y √ d < (x 1 + После умножения на (x 1 + y 1 √ d) −n = x n − y n √ d получим < (x + y √ d)(x n − y n √ d) < x 1 + Положим (x + y √ d)(x n − y n √ d) = X + Y √ d. Чтобы прийти к противоречию, достаточно показать, что X 2 − dY 2 = 1 и X > 0, Y > По условию (x + y √ d)(x − y √ d) = 1 и (x n − y n √ d)(x n + y n √ d) = поэтому (X + Y √ d)(X − Y √ d) = 1, те. Кроме того+ Y √ d > 1, а значит, 0 < X − Y √ d < 1. Следовательно = (X + Y √ d) + (X − Y √ d) > 1 + 0 > 0, 2Y √ d = (X + Y √ d) − (X − Y √ d) > 1 − 1 = 0. Глава 12. Уравнения в целых числах. Ясно, что d имеет простой делитель p = 4k + 3. Предположим, что x 2 − dy 2 = −1. Тогда x 2 ≡ −1 (mod p), поэтому число является квадратичным вычетом по модулю p. С другой стороны, если p = 4k + 3 — простое число, то согласно задаче 31.36 число не является квадратичным вычетом по модулю p. 12.23. Пусть (x 1 , y 1 ) — фундаментальное решение уравнения Пелля x 2 −dy 2 = 1. Из условия d ≡1 (mod 4) вытекает, что x 2 1 −y 2 1 ≡ ≡ 1 (mod 4). Следовательно, x 1 ≡ 1 (mod 2) и y 1 ≡ 0 (mod 2). Перепишем равенство x 2 1 − dy 2 1 = 1 в виде 2 · x 1 − 1 2 = d “ y 1 По условию число d простое, поэтому либо 2 = da 2 , x 1 − 1 2 = либо 2 = a 2 , x 1 − 1 2 = В первом случае получаем b 2 − da 2 = −1. Во втором случае получаем, что противоречит минимальности решения (x 1 , y 1 ). 12.24. Положим+ Y √ d = “ x + те Согласно задаче 4.42 г) x 2 ≡ 1 (mod 8) и y 2 ≡ 1 (mod 8). Следовательно, а значит, x 2 + 3dy 2 ≡ 1 + 15 ≡ 0 (mod и 3x 2 + dy 2 ≡ 3 + 5 ≡ 0 (mod 8), поэтому числа X и Y целые. Кроме того+ Y √ d = “ x + y p d 2 ” 3 “ x − y p d 2 ” 3 = −1. 12.25. Предположим сначала, что среди чисел m, n и p есть равные, например, n = p. Тогда m 2 + 2n 2 = 3mn 2 , те+ Следовательно, m = dn, где d — целое число. При этом d 2 + 2 = те. Поэтому d = 1 или 2. В обоих случаях n = В результате получаем решения (1, 1, 1) и (2, 1, 1). Назовём их особыми. Возьмём теперь неособое решение (m, n, p), для которого числа, n, p попарно различны, и рассмотрим квадратный трёхчлен f(x) = x 2 − 3xnp + n 2 + Ясно, что f(m) = 0, те. один корень квадратного трёхчлена равен m. Второй его корень можно найти по теореме Виета: Решения задач 3np − m. Ясно, что при этом (m ′ , n, p) — решение уравнения. Покажем, что наибольшее из чисел n и p заключено между m и m ′ . Пусть для определённости n > p. Тогда m)(n − m ′ ) = f(n) = 2n 2 + p 2 − 3n 2 p < Это как рази означает, что n заключено между m и Аналогичным образом по решению (m, n, p) можно построить решения (m, n ′ , p) и (m, n, Предположим, что m — наибольшее из чисел m, n, p. Тогда > max(n, p) > m ′ , n < m = max(m, p) < Таким образом, при переходе отрешения) к решению, n, p) наибольшее из трёх чисел уменьшается, а при переходе к решениями) увеличивается. Если начинать с решения (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, Это дерево содержит все решения, поскольку от произвольного решения после нескольких уменьшений максимума мы перейдём к особому решению. Под уменьшением максимума мы подразумеваем переход отрешения, где m > max(n, p), к решению, n, p). 12.26. Достаточно доказать, что если m 2 + n 2 + p 2 = mnp, то числа m, n и p делятся на 3. Если целое число не делится на то его квадрат при делении на 3 даёт остаток 1. Поэтому если+ n 2 + не делится на 3, то среди чисел m, n и p есть как делящиеся на 3, таки не делящиеся на 3. Но тогда m 2 + n 2 + p 2 = mnp Глава 12. Уравнения в целых числах делится на 3, чего не может быть. Значит, m 2 + n 2 + делится на 3, причём числа m, n и p одновременно либо все делятся на либо все не делятся на 3. Второй вариант невозможен, потому что m 2 + n 2 + делится на 3. 12.27. Случай k = 2 — это задача 12.13 а. Поэтому будем предполагать, что k > 3. Предположим, что x 2 + y 2 + z 2 = kxyz, где x, y, z — натуральные числа. Прежде всего покажем, что эти числа попарно различны. Пусть y = z. Тогда x 2 = kxy 2 − 2y 2 = (kx − поэтому x = l y, где l — натуральное число. При этом l 2 = k l y − те. Значит 1 или 2. В обоих случаях ky = 3, что противоречит неравенству k > Пусть для определённости x > y > z. Рассмотрим квадратный трёхчлен f(t) = t 2 − kyzt + y 2 + z 2 . Один его корень равен а второй корень по теореме Виета равен kyz − x. Ясно, что x)(y − x ′ ) = f(y) = 2y 2 + z 2 − ky 2 z < 0, те. Таким образом, по решению x, y, z мы построили новое решение x ′ , y, для которого x ′ , y, z < x. Повторяя эту конструкцию x раз, приходим к противоречию. (Решающее отличие от уравнения Маркова состоит в том, что здесь нет решения с двумя одинаковыми числами, поэтому операцию уменьшения решения можно применять бесконечно много раз. Предположим, что m = dm 1 , n = и p = dp 1 , где d > Тогда m 2 1 + n 2 1 + p 2 1 = 3dm 1 n 1 p 1 . Но согласно задаче 12.27 уравнение+ y 2 + z 2 = kxyz не имеет решений в натуральных числах при > 3. ГЛАВА ИНДУКЦИЯ. Вычисление сумм. Вычислите сумму 2! + 2 3! + 3 4! + . . . + n − 1 n! 13.2. Вычислите сумму · 1! + 2 · 2! + 3 · 3! + . . . + n · n!. 13.3. Докажите, что 1 3 + 2 3 + 3 3 + . . . + m 3 = m(m + 1) 2 2 13.4. Докажите, что − 1 2 + 1 3 − 1 4 + . . . − 1 2n = 1 n + 1 + 1 n + 2 + . . . + 1 2n 13.2. Неравенства. Докажите неравенство · 1! + 2 · 2! + 3 · 3! + . . . + k · k! < (k + 1)!. 13.6. Докажите, что если 0 < x 1 , . . ., x n < 1 и n > 2, то x 1 ) . . . (1 − x n ) > 1 − (x 1 + . . . + x n ). 13.7. Докажите, что прицелом и |x| < 1 2 n > (1 − x) n + (1 + x) n 13.8. Докажите, что + 1 2 1 + 1 4 1 + 1 8 . . . 1 + 1 2 n < 3. Глава 13. Индукция. а) Докажите, что для любого a > 0 и любого натурального выполняется неравенство (1 + a ) n > 1 + n a б) Докажите, что если 0 < a 6 1/n и n — натуральное число, то выполняется неравенство (1 + a ) n < 1 + n a + n 2 a 2 13.10. Докажите неравенство между средним арифметическими средним геометрическим для n положительных чисел (a 1 a 2 . . . a n ) 1/n 6 (a 1 + . . . + a n )/n, причём равенство достигается, только если a 1 = . . . = a n 13.11. Докажите, что для любого натурального 3. 13.12. Докажите неравенство − n раз z }| { r 2 + q 2 + . . . + √ 2 2 − r 2 + q 2 + . . . + √ 2 | {z } n −1 раз 4 13.3. Доказательство тождеств. Некоторые из чисел a 1 , a 2 , . . ., равны +остальные равны −1. Докажите, что sin a 1 + a 1 a 2 2 + a 1 a 2 a 3 4 + . . . + a 1 a 2 . . . a n 2 n −1 p 4 = = a 1 s 2 + a 2 r 2 + a 3 q 2 + . . . + a n √ 2. 13.4. Разные задачи. На кольцевой автомобильной дороге стоит несколько одинаковых автомобилей. Известно, что если весь бензин, находящийся в автомобилях, слить в один из них, то этот автомобиль сможет проехать по всей кольцевой дороге и вернуться на прежнее место. Докажите, что хотя бы один Решения задач 173 из этих автомобилей сможет проехать по всей кольцевой дороге в заданном направлении, забирая по пути бензину остальных автомобилей. Докажите, что любую дробь m/n, где 0 < m/n < можно представить в виде+ . . . где 0 < q 1 < q 2 < . . . < q r , причём число делится на при 2, 3, . . . , См. также задачу Решения. Докажем индукцией по n, что рассматриваемая сумма равна 1 − 1 n! . При n = 2 получаем очевидное равенство 2! = 1 − 1 Предположим, что требуемое равенство доказано для некоторого. Тогда 2! + 2 3! + . . . + n − 1 n! + n (n + 1)! = 1 − 1 n! + n (n + 1)! = = 1 − n + 1 (n + 1)! + n (n + 1)! = 1 − 1 (n + 1)! 13.2. Докажем индукцией по n, что рассматриваемая сумма равна (n + 1)! − 1. При n = 1 получаем очевидное равенство · 1! = 2! − 1. Предположим, что требуемое равенство доказано для некоторого n. Тогда · 1! + 2 · 2! + . . . + n · n! + (n + 1) · (n + 1)! = = (n + 1)! − 1 + (n + 1) · (n + 1)! = (n + 2)! − 1. 13.3. База индукции очевидна, поэтому нужно лишь проверить равенство + 1) 2 4 + (m + 1) 3 = (m + 1) 2 (m + 2) 2 После деления на m + 1 и умножения на 4 получаем очевидное равенство m 2 + 4(m + 1) = (m + 2) 2 Глава 13. Индукция. Пусть A n = 1 − 1 2 + 1 3 − 1 4 + . . . − 1 и B n = 1 n + 1 + 1 n + 2 + . . . . . . + 1 2n . Тогда A n +1 = A n + 1 2n + 1 − 1 2n + и B n +1 = B n − 1 n + 1 + + 1 2n + 1 + 1 2n + 2 . Значит, A n +1 − B n +1 = A n − B n + 1 n + 1 − 2 2n + 2 = = A n − B n . Равенство A 1 = очевидно, поэтому A n = для всех 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−x 1 ) × ×(1 − x 2 ) = 1 − (x 1 + x 2 ) + x 1 x 2 > 1 − (x 1 + x 2 ). Предположим, что x 1 ) . . . (1 − x n −1 ) > 1 − (x 1 + . . . + x n −1 ). Тогда (1 − x 1 ) . . . (1 − x n ) > > 1 − x n − (x 1 + . . . + x n −1 ) + x n (x 1 + . . . + x n −1 ) > 1 − (x 1 + . . . + x n ). 13.7. Применим индукцию по n. При n = 2 получаем (1 − x) 2 + + (1 + x) 2 = 2(1 + x 2 ) < 4. Предположим теперь, что (1 − x) n + + (1 + x) n < 2 n . Тогда x) n +1 + (1 + x) n +1 < ((1 − x) n + (1 + x) n )((1 − x) + (1 + x)) < < 2 n · 2 = 2 n +1 13.8. Требуемое неравенство эквивалентно неравенству + 1 4 ”“ 1 + 1 8 ” . . . “ 1 + 1 Если 0 < x < 1, то 0 < 1 − x 2 < 1, поэтому 1 + x < 1 1 − x . Значит + 1 2 k ” < “ 1 − 1 2 k ” −1 . Воспользовавшись неравенством из задачи, получаем − 1 4 ”“ 1 − 1 8 ” . . . “ 1 − 1 2 n ” > 1 − 1 4 − 1 8 − . . . − 1 2 n > 1 2 |