Уравнения 1-ой степени

Диофантовым уравнением 1-ой степени (линейным) с n неизвестными называется уравнение вида
a1x1+a2x2++anxn=b
где все коэффициенты и неизвестные – целые числа и хотя бы одноai0.Решением линейного диофантова уравнения называется упорядоченная n-ка целых чисел(x1,x2,,xn), такая, чтоa1x1+a2x2++anxn=b.Теорема. При взаимно простых коэффициентахa1,a2,,an диофантово уравнение
a1x1+a2x2++anxn=1
имеет решение в целых числах.
Доказательство. Обозначим через множество M тех положительных чисел b, для которых уравнение
a1x1+a2x2++anxn=b
имеет решение в целых числах. M, очевидно, не пусто, так как при заданных a1,a2,,an, можно подобрать целые значения x1,x2,,xn, такие, чтобыa1x1+a2x2++anxn было положительным числом.В множестве M существует наименьшее число (M – подмножество натуральных чисел), которое мы обозначим через d (dM). Обозначим через x1,x2,,xn-целые числа, такие, что
a1x1+a2x2++anxn=d.
Пусть a1=dq+r, где 0rd, тогда
r=a1(a1x1+a2x2++anxn)q==a1(1qx1)+a2(qx2)++an(qxn).
Мы подобрали целые значения:x1=1qx1,x2=qx2,,xn=qxn, такие, что a1x1+a2x2++anxn=r, но 0rd, а d – наименьшее положительное число вM, т. е. r не может быть положительным,r=0,a1=dq,a1d.Теперь пусть a2=dq+r, 0rd, тогда
r=a2(a1x1+a2x2++anxn)q==a1(qx1)+a2(1qx2)++an(qxn).
Мы подобрали целые значения:x1=qx1,x2=1qx2,,xn=qxn, такие, что a1x1+a2x2++anxn=r, но 0rd, а d-наименьшее положительное число в M,т. е. r не может быть положительным,r=0,a2=dq,a2d.Аналогично получаем: a3d,,and.Мы видим, что d – общий делитель чисел a1,a2,,an, следовательно, поскольку(a1,a2,,an)=1,1d,d=1,1inM, то уравнение разрешимо в целых числах. Теорема. (Теорема о решении ЛДУ). Пусть d - наибольший общий делитель коэффициентов a1,a2,,an. Диофантово уравнение имеет решение тогда, и только тогда, когда db.Доказательство. Последовательно рассмотрим и докажем все три утверждения теоремы.

  1. Пусть bd. Для уравнения
    a1dx1+a2dx2++andxn=1,
    Где (a1d,a2d,and)=1, существуют целые числа: c1,c2,,cn, удовлетворяющие ему.Т.е. такие, что
    a1dc1+a2dc2++andcn=1
    Тогда
    a1(a1dc1)+a2(a2dc2)++an(andcn)=b,
    т. е. (c1bd,c2bd,,cnbd)- решение уравнения.
  2. Пусть теперь d не делит b. Тогда левая часть уравнения при любых целых x1,x2,,xn делится на d, а правая на d не делится, так что равенство при целых значениях x1,x2,,xn невозможно.
  3. Если (x1,x2,,xn) - упорядоченная n-ка чисел, удовлетворяющая уравнению, то например, все n-ки(x1+a2t,x2a1t,x3,,xn) при t=0,±1,±2,также удовлетворяют этому уравнению и, таким образом, у нас либо совсем не будет решений, либо их будет бесконечное множество.Если хоть одна пара коэффициентов взаимно простая, то d=1, и уравнение имеет бесчисленное множество решений.
Теорема. Пусть a и b взаимно простые числа и x1,y1- какое-нибудь решение уравнения
ax+by=c.(1)
Тогда формулы
x=x1+bt,y=y1at(2)
при t=0,±1,±2, дают все решения (1).
Доказательство. Так как
ax1+by1=c,(3)
то из (1) и (3) имеемaxax1+byby1=0. Отсюда
a(xx1)b=y1y.
Но поскольку y1y – целое и (a,b)=1, то xx1 должно делиться на b, то есть
xx1=bt,(4)
и, следовательно,
y1y=at.(5)
Из (4) и (5) получаем, что
x=x1+bt,y=y1at.
Теперь покажем, что всякие пары чисел (x,y), получаемые по формулам (2), также являются решениями уравнения(1). Действительно,
ax+by=a(x1+bt)+b(y1at)=ax1+abt+by1bat=ax1+by1=c.
Таким образом, все решения уравнения (1) исчерпываются числами, получаемыми по формулам (2).