Решение уравнения в целых числах для целых чисел

Теорема 18.1. Уравнение , где - целые числа, разрешимо в целых числах тогда и только тогда, когда делится на наибольший общий делитель целых чисел . При этом, если пара - целое решение уравнения (∗), то все его целые решения получаются по формулам: , где - произвольное целое число.

Следствие. Если в уравнении (∗) числа взаимно просты (), то все целые решения этого уравнения находятся по формулам: , где - произвольное целое число.

Пример 12. Группа учащихся отправилась в театр, причём часть из них отправилась на автобусе с ценой билета 17 рублей, а вторая - на маршрутке с ценой билета 23 рубля. Всего за проезд в театр заплатили 455 рублей. Сколько учащихся было в этой группе?

Обозначим через количество учащихся, поехавших на маршрутке, а через - на автобусе. Требуется решить уравнение (∗) в неотрицательных целых числах (количество учащихся не может быть отрицательным). Заметим, что (23,17)=1.

Замечание. Если бы НОД(23,17) не равнялся 1, то обе части уравнения нужно было бы сократить на этот НОД. Число 455 не делится на 23 и на 17, поэтому решения не могут быть нулевыми, а значит, только натуральными.

Решим уравнение в целых числах. Уравнение (∗) разрешимо в целых числах. Но вначале найдём хотя бы одно целое решение уравнения (∗∗) . Воспользуемся алгоритмом линейного выражения (23,17) из пункта 3:

23=17∙1+6; .

17=6∙2+5; .

6=5∙1+1; .

5=1∙5+0; .

1= =(23,17)= .

Значит, 23∙3+17∙(-4)=1, т.е. - целые решения уравнения (∗∗). Помножим обе части полученного равенства на 455:

23∙(3∙455)+17∙((-4)∙455)=1∙455, т.е. 23∙1365+17∙(-1820)=455.

Тогда пара (1365;-1820)-целое решение уравнения (∗). Теперь из полученного целого решения уравнения (∗) найдём все его натуральные решения, если они существуют.

Для этого в последнем равенстве в левой его части будем из первого слагаемого перекидывать положительные числа во второе, но так, чтобы: 1) множители при числе 23 в первом слагаемом оставались положительными; 2) множители при числе 17 во втором слагаемом стали положительными; 3) перекидываемые числа должны быть кратны 17. Например, из первого слагаемого во второе можно перекидывать числа 23∙17, 23∙(2∙17), 23∙(3∙17) и т.д. Чтобы множитель при числе 17 во втором слагаемом сделать первый раз положительным, нужно взять минимальное натуральное число такое, что . Тогда . Получаем:

23∙1365+17∙(-1820)=455 23∙(1365-17∙80)+23∙17∙80+17∙(-1820)=455

23∙5+17∙(23∙80-1820)=455 23∙5+17∙20=455. Заметим, что из первого слагаемого во второе уже нельзя перекидывать числа, для которых выполняются все три условия выше. Поэтому равенство 23∙5+17∙20=455 единственное с натуральными сомножителями при числах 23 и 17. Значит, уравнение имеет единственное натуральное решение и - количество учащихся в группе, поехавшей в театр.