Глава

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

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

Теория

1. Что такое диофантово уравнение? Диофантово уравнение - это уравнение, в котором решения ищутся в целых числах, иногда в положительных целых числах. Например, \[ 3x+5y=17 \] в теории чисел означает: найти целые пары \((x,y)\). 2. Линейные диофантовы уравнения Уравнение \[ ax+by=c \] имеет целые решения тогда и только тогда, когда \[ \gcd(a,b)\mid c. \] Это условие необходимо, потому что любой общий делитель \(a\) и \(b\) делит \(ax+by\). Оно также достаточно: алгоритм Евклида позволяет представить \(\gcd(a,b)\) как линейную комбинацию \(a\) и \(b\). 3. Общее решение Если \((x_0,y_0)\) - одно решение уравнения \(ax+by=c\), а \(g=\gcd(a,b)\), то все целые решения имеют вид \[ x=x_0+\frac{b}{g}t,\qquad y=y_0-\frac{a}{g}t, \] где \(t\) - целое число. 4. Метод факторизации Многие диофантовы уравнения становятся проще после разложения: \[ xy+x+y=11 \] можно переписать как \[ (x+1)(y+1)=12. \] После этого решения дают целые делители числа \(12\). 5. Препятствия по модулю Иногда уравнение не имеет целых решений из-за остатков. Например, если квадрат не может давать нужный остаток по модулю \(3\) или \(4\), уравнение невозможно. 6. Неотрицательные и положительные решения В олимпиадных задачах часто ищут положительные или неотрицательные решения. После получения параметрического вида ограничения на знак ограничивают параметр.

Примеры

Пример 1. Проверка целых решений Это первое препятствие: НОД должен делить свободный член. Задача. Определите, имеет ли уравнение \(6x+10y=15\) целые решения. Решение. \(\gcd(6,10)=2\). Левая часть всегда четна, а \(15\) нечетно. Поэтому целых решений нет. Пример 2. Одно решение Безу Свяжите это напрямую с алгоритмом Евклида из модуля 2. Задача. Найдите одно целое решение уравнения \(3x+5y=1\). Решение. Так как \(2\cdot3-1\cdot5=1\), одно решение: \((x,y)=(2,-1)\). Пример 3. Все линейные решения Подчеркните, что параметр двигает точку по прямой, не меняя значение. Задача. Найдите все целые решения уравнения \(3x+5y=17\). Решение. Одно решение: \((4,1)\), потому что \(3\cdot4+5\cdot1=17\). Так как \(\gcd(3,5)=1\), все решения имеют вид \(x=4+5t\), \(y=1-3t\), где \(t\in\mathbb Z\). Пример 4. Уравнение на пары множителей Задачи на пары множителей тренируют полноту решения. Задача. Решите \(xy=18\) в положительных целых числах. Решение. Положительные пары множителей: \((1,18),(2,9),(3,6),(6,3),(9,2),(18,1)\). Пример 5. Довести до произведения Это важный олимпиадный прием факторизации. Задача. Решите \(xy+x+y=11\) в положительных целых числах. Решение. Перепишем как \((x+1)(y+1)=12\). Так как \(x,y>0\), оба множителя не меньше \(2\). Пары: \((2,6),(3,4),(4,3),(6,2)\), поэтому \((x,y)=(1,5),(2,3),(3,2),(5,1)\). Пример 6. Разность квадратов Следите, чтобы ученики не забывали отрицательные пары множителей. Задача. Найдите все целые решения уравнения \(x^2-y^2=15\). Решение. Пусть \(a=x-y\), \(b=x+y\). Тогда \(ab=15\), причем \(a,b\) одной четности. Пары множителей нечетные: \((1,15),(3,5),(5,3),(15,1)\) и их отрицательные пары. Из \(x=(a+b)/2\), \(y=(b-a)/2\) получаем \((8,7),(4,1),(4,-1),(8,-7)\) и соответствующие отрицательные пары \((-8,-7),(-4,-1),(-4,1),(-8,7)\). Пример 7. Препятствие по модулю Эта задача связывает модуль 4 с диофантовыми уравнениями. Задача. Докажите, что уравнение \(x^2+y^2=4z+3\) не имеет целых решений. Решение. Квадраты дают \(0\) или \(1\pmod4\). Поэтому \(x^2+y^2\) может давать \(0,1\) или \(2\pmod4\), а \(4z+3\equiv3\pmod4\). Противоречие. Пример 8. Произведение плюс сумма Ученикам может понадобиться помощь в подборе сдвинутых множителей. Задача. Найдите все целые решения уравнения \(xy-2x+3y=7\). Решение. Имеем \((x+3)(y-2)=xy-2x+3y-6\). Так как \(xy-2x+3y=7\), получаем \((x+3)(y-2)=1\). Значит, \((x+3,y-2)=(1,1)\) или \((-1,-1)\). Решения: \((-2,3)\) и \((-4,1)\).

Задачи

Пока нет опубликованных задач.

Лестницы

Опубликованных лестниц пока нет.

Предыдущая глава

Следующая глава