Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

 

Линейное диофантово уравнение – это уравнение вида

 

 a₁ * x₁ + a₂ * x₂ +…+ a_n *x_n = b          

 

где a₁ , a₂ , …, a_n и b – целые числа и решение x₁ , x₂ , … , x_n тоже ищется во множестве целых чисел.

Сначала рассмотрим решение диофантова уравнения с двумя неизвестными [34]

 

a*x +b*y = c                                                                                      (3) 

 

Для существования решений необходимо и достаточно, чтобы правая часть c делилась на наибольший общий делитель НОД(a,b) чисел a и b. Необходимость очевидна: поскольку левая часть равенства делится на НОД(a,b), то и правая часть этого равенства тоже должна делиться на это же число.

С помощью алгоритма Евклида помимо НОД(a,b) можно найти и такие числа r и s , для которых выполняется равенство 

 

a*r + b*s = НОД(a,b)

 

Тогда частным решением уравнения (3) является следующая пара чисел:

 

X₀ = r*c/ НОД(a,b)

Y₀ = s*c/ НОД(a,b)

 

Рассмотрим решение однородного уравнения 

 

a*r + b*s = 0

 

Разделим обе части равенства на НОД(a,b) .

 

(a/ НОД(a,b))*r + (b/ НОД(a,b))*s = 0                                                    (4)

 

Заметим, что числа a/ НОД(a,b) и b/ НОД(a,b) целые и взаимно простые. Первое слагаемое равенства (4) делится на a/ НОД(a,b) – следовательно, и второе слагаемое тоже должно делиться на это же выражение. Но, поскольку числа a/ НОД(a,b) и b/ НОД(a,b) взаимно просты, число s должно делиться на число a/ НОД(a,b) . Значит, существует такое целое число t , что

 

s = ( a/ НОД(a,b) ) * t 

 

тогда

 

r = - ( b/ НОД(a,b) ) * t 

 

Итак, для любого t Î Z решением уравнения (3) является пара чисел

 

X = - ( b/ НОД(a,b) ) * t + X₀  

                                                                                                             (5) 

Y = ( a/ НОД(a,b) ) * t + Y₀ 

 

(Это легко проверяется подстановкой этих равенств в (3) ).

 

a*X +b*Y = c                                                                                          (6) 

 

Докажем, что других решений не существует. Действительно, предположим, что пара чисел u и v  – некоторое решение уравнения (3). Тогда выполняется равенство

 

a*u +b*v = c              

 

Вычтем это равенство из равенства (6):

 

a*(X-u) +b*(Y-v) = 0              

 

Получено однородное уравнение с коэффициентами a и b . Общее решение этого уравнения имеет вид               

 

X - u = - ( b/ НОД(a,b) ) * w 

 

Y - v = ( a/ НОД(a,b) ) * w   w Î Z. 

 

Тогда, подставляя значения X и Y, получим

 

u = - ( b/ НОД(a,b) ) * t + X₀ + ( b/ НОД(a,b) ) * w 

 

v = ( a/ НОД(a,b) ) * t + Y₀  - ( a/ НОД(a,b) ) * w   w Î Z. 

 

или

 

u = - ( b/ НОД(a,b) ) * z + X₀

 

v = ( a/ НОД(a,b) ) * z + Y₀     

 

где z = (t - w ) Î Z. 

 

Таким образом, решения u и v имеют такой же вид, как и (5).

 

Следствие. Линейная функция двух целых переменных a*x +b*y с целыми коэффициентами принимает множество значений вида НОД(a,b) * w, w Î Z.

Доказательство: Действительно, для каждого w Î Z уравнение 

 

a*x +b*y = НОД(a,b) * w

 

имеет решение. С другой стороны, если правая часть уравнения (3) не представима в таком виде, т.е. не делится на НОД(a,b), то уравнение не имеет решений.

 

Теорема 1. Уравнение

 

a₁*x₁ +a₂ *x₂ +…+a_n *x_n = c                                                          (7) 

 

имеет решение тогда и только тогда, когда число c делится на НОД(a₁,a₂,…,a_n) . Общее решение этого уравнения имеет вид

 

x₁ = g₁₁  * t₁ + g₁₂ t₂ + … + g_1(n-1) * t_n-1           

…                                                                                                  (8)  

x_n = g_n1  * t₁ + g_n2 t₂ + … + g_n(n-1) * t_n-1 

 

 где t₁ , t₂ , … t_n-1 пробегают множество целых чисел Z .

 

Доказательство проведем методом математической индукции.

Для n=2 теорема уже доказана выше.

Предположим, что теорема верна для n=k.

Докажем теорему для n=k+1.

Сгруппируем в левой части уравнения два последних слагаемых.

 

a₁*x₁ +a₂ *x₂ +…+ (a_k *x_k + a_k+1 *x_k+1 ) = c

 

Выражение (a_k *x_k + a_k+1 *x_k+1) принимает значения вида НОД(a_k, a_k+1) * w , где w – некоторая переменная, пробегающая множество целых чисел. Подставим это выражение в исходное уравнение и получим следующее: 

 

a₁*x₁ +a₂ *x₂ +…+ a_k-1 *x_k-1 + НОД(a_k, a_k+1) * w = c

 

Согласно предположению индукции, это уравнение имеет решение тогда и только тогда, когда число c делится на следующую величину

 

НОД(a₁,a₂,…,a_k-1, НОД(a_k,a_k+1) ) = НОД(a₁,a₂,…,a_n)        

 

и это решение имеет вид     

 

x₁ = g₁₁  * t₁ + g₁₂ t₂ + … + g_1(k-1) * t_k-1           

…

x_k-1 = g_(k-1)1  * t₁ + g_(k-1)2 t₂ + … + g_(k-1)(k-1) * t_k-1 

w = g_k1  * t₁ + g_k2 t₂ + … + g_k(k-1) * t_k-1           

 

где t₁ , t₂ , … t_k-1 пробегают множество целых чисел Z .

 

Рассмотрим последнее уравнение, заменив w исходным выражением

 

(a_k *x_k + a_k+1 *x_k+1 ) = g_k1  * t₁ + g_k2 t₂ + … + g_k(k-1) * t_k-1           

 

и решим это равенство относительно x_k и x_k+1 :

 

x_k = -(a_k+1/НОД(a_k, a_k+1))*t_k + r*(g_k1*t₁ + g_k2t₂ + … + g_k(k-1)*t_k-1)/НОД(a_k, a_k+1) 

 

x_k+1 = (a_k/НОД(a_k,a_k+1))*t_k + s*(g_k1*t₁ + g_k2t₂ + … + g_k(k-1)*t_k-1)/НОД(a_k, a_k+1)   

 

Здесь r, s – константы, которые находятся алгоритмом Евклида, а переменная t_k пробегает множество целых чисел. Заменяя этими двумя равенствами в системе равенство для переменной w, получим систему равенств искомого вида

 

x₁ = g₁₁  * t₁ + g₁₂ t₂ + … + g_1(k-1) * t_k-1           

…

x_k-1 = g_(k-1)1  * t₁ + g_(k-1)2 t₂ + … + g_(k-1)(k-1) * t_k-1 

x_k = -(a_k+1/НОД(a_k, a_k+1))*t_k + r*(g_k1*t₁ + g_k2t₂ + … + g_k(k-1)*t_k-1)/НОД(a_k, a_k+1) 

x_k+1 = (a_k/НОД(a_k,a_k+1))*t_k + s*(g_k1*t₁ + g_k2t₂ + … + g_k(k-1)*t_k-1)/НОД(a_k, a_k+1)   

 

Конец доказательства.

 

Следствие. Линейная функция целых переменных a₁*x₁ +a₂ *x₂ +…+a_n *x_n    с целыми коэффициентами принимает множество значений вида

 НОД(a₁,a₂,…,a_n) * w, w Î Z.