№19. Задачи на олимпиадные темы

Диофантовы уравнения

Запоминайте формулы по каждой теме

Осваивайте новые концепции ежедневно

Вдумывайтесь в теоретические материалы

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела: №19. Задачи на олимпиадные темы

Теоретическая справка

#576

Линейные диофантовы уравнения с двумя неизвестными

Определение Однородным линейным диофантовым уравнением с двумя неизвестными называется уравнение вида $ax+ by = 0,$ где $a,b∈ ℤ$ и $(a,b) =1.$

Теорема

Если $a$ и $b$ — взаимно простые числа, то уравнение $ax+ by = 0$ имеет бесконечно много решений в целых числах, а именно каждая пара чисел $x = bu$ и $y = − au$ для любого $u ∈ℤ$ является решением этого уравнения.

1. Решите в целых числах уравнение $40x = 63y.$

Решение.

Заметим, что числа 40 и 63 взаимно просты. Следовательно, так как левая часть, то есть выражение $40x,$ делится на 40, то и правая часть должна делиться на 40. Отсюда следует, что $y$ делится на 40. Следовательно, можно представить $y = 40u,$ $u∈ ℤ.$ Тогда уравнение примет вид $40x= 63⋅40u,$ откуда $x = 63u.$ Получаем, что любая пара $(63u;40u),$ где $u∈ ℤ,$ является решением данного уравнения.

Определение Неоднородным линейным диофантовым уравнением с двумя неизвестными называется уравнение вида $ax+ by = c,$ где $a,b,c ∈ℤ.$

Теорема

Если $(a,b)= d> 1$ и число $c$ не делится на $d,$ то уравнение $ax + by = c$ не имеет решений в целых числах.

Доказательство

Действительно, если $d >1$ — НОД чисел $a$ и $b,$ то сумма $ax+ by$ делится на $d.$ Следовательно, так как левая часть уравнения $ax + by = c$ делится на $d,$ то и правая часть должна делиться на $d.$ Но $c$ не делится на $d,$ значит, не существует таких значений для неизвестных $x$ и $y,$ которые будут удовлетворять этому уравнению.

Теорема

Любое уравнение вида $ax+ by = c,$ где $(a,b) =1$ и $a,b,c ∈ℤ,$ имеет решения в целых числах, которые описываются формулой $x= x0+ bu$ и $y = y0 − au,$ $u∈ ℤ,$ где $(x0;y0)$ — некоторое частное решение этого уравнения.

Рассмотрим на примере, как находить решение подобного рода уравнений.

2. Решите в целых числах уравнение $3x + 5y = 7.$

Решение. Найдем частное решение этого уравнения: $x = 4 0$ и $y = − 1. 0$ Действительно, $3 ⋅4+ 5⋅(− 1)= 7.$ Тогда общее решение этого уравнения записывается как $x =4 +5u$ и $y = −1 − 3u,$ $u∈ ℤ.$

Рассмотрим еще одно неоднородное линейное диофантово уравнение, в котором решения будут найдены несколько другим способом.

3. Фирма продавала чай в центре города по 7 рублей, а кофе по 10 рублей стакан, на вокзале по 4 рубля и 9 рублей соответственно. Всего было продано за час 20 стаканов чая и 20 стаканов кофе, при этом выручка в центре и на вокзале оказалась одинаковой. Сколько стаканов кофе было продано в центре?

Решение. Пусть $x$ и $y$ — число стаканов чая и кофе соответственно, проданных в центре города. Тогда на вокзале продано $20− x$ и $20− y$ стаканов чая и кофе соответственно. Следовательно, $x,y ∈ ℕ ∪{0},$ причем $x≤ 20,$ $y ≤20.$

Выручка в центре города составила $7x + 10y,$ а на вокзале $4(20 − x) +9(20− y).$ По условию выручка в центре города и на вокзале оказалась одинаковой, следовательно, получаем уравнение

7x+ 10y = 4(20 − x)+ 9(20− y) ⇔ 11x +19y =260.

Получили неоднородное уравнение первой степени, которое необходимо решить в целых числах.

В данном уравнении подбором сложно определить частное решение, поэтому мы поступим другим образом. Выразим из этого уравнения ту неизвестную, коэффициент перед которой наименьший, то есть $x :$

x= 260-− 19y-= 23 − y+ 7−-8y. 11 11

Так как $x ∈ℤ,$ то правая часть должна представлять собой целое число. Так как $y ∈ ℤ,$ то $23 − y ∈ ℤ,$ следовательно, дробь $7−18y1-$ также должна быть целым числом. Рассмотрим остатки при делении на 11 числа $y.$ Мы имеем 11 различных остатков: 0, 1, 2, …, 9, 10. Определим, какой остаток при делении на $11$ должно иметь число $y,$ чтобы дробь $7−118y-$ была целым числом.

Если $y ≡ 0 (mod 11),$ то $y = 11k,$ $k ∈ℤ,$ следовательно, $7−8y 7 -11-= 11 − 8k$ — нецелое число.

Если $y ≡ 1 (mod 11),$ то $y = 1+ 11k,$ $k ∈ ℤ,$ и тогда $7−8y 7−8−8⋅11k -1 11 = 11 = −11 − 8k$ — нецелое число.

Продолжая аналогично, находим, что если $y ≡ 5 (mod 11),$ то есть $y = 5+ 11k,$ $k ∈ ℤ,$ то $7−8y-= 7−40−8⋅11k= −3 − 8k 11 11$ — целое число. Значит, $y = 5+ 11k,$ $k ∈ ℤ.$ Но тогда

x =23 − y + 7−-8y= 23− 5− 11k− 3− 8k = 15− 19k. 11

Так как $x,y ∈ {0;1;2;...;19;20},$ то $k$ может быть только равен нулю. Следовательно, из $k = 0$ получаем $x= 15$ и $y = 5.$

Ответ: в центре было продано 5 стаканов кофе.

Произвольные диофантовы уравнения, решающиеся через делимость

4. Решить в целых числах уравнение $xy+ 3x− 5y = −3.$

Решение. Перепишем уравнение в виде

x(y+ 3)− 5(y+ 3)= −3 − 15 ⇔ (x − 5)(y+ 3)= −18.

Пусть $x − 5 = a,$ $y+ 3= b.$ Тогда $a,b∈ ℤ$ и уравнение примет вид

ab =− 18.

Делители числа $18$ — это числа 1, 2, 3, 6, 9, 18. Следовательно, в качесте пар $(a;b)$ нам подходят пары $(1;− 18),$ $(− 1;18),$ $(2;− 9),$ $(−2;9),$ $(3;− 6),$ $(−3;6),$ $(6;−3),$ $(− 6;3),$ $(9;−2),$ $(− 9;2),$ $(18;−1)$ и $(− 18;1).$ Следовательно, так как $x = a+ 5,$ $y = b− 3,$ то для $(x;y)$ получаем пары $(6;−21),$ $(4;15),$ $(7;− 12),$ $(3;6),$ $(8;−9),$ $(2;3),$ $(11;− 6),$ $(− 1;0),$ $(14;− 5),$ $(− 4;− 1),$ $(23;−4)$ и $(−13;−2).$

Предыдущая справка

Следующая справка