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

Теорема 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)=45523∙(1365-17∙80)+23∙17∙80+17∙(-1820)=455

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

11. Признаки делимости.

Определение.Критерий, устанавливающий необходимые и достаточные условия делимости произвольного натурального числана данное натуральное число, называетсяпризнаком делимости на .

Различают общие признаки, имеющие силу для любого , и частные – для отдельных значений.

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

Теорема 19.1.(Общий признак делимости Паскаля). Для того, чтобы натуральное число, записанное в произвольной-ичной системе счисления в виде, делилось на натуральное число, необходимо и достаточно, чтобы числоделилось на, где- цифры числа, записанного в-ичной системе счисления,- остатки от деленияна.

Частные признаки делимости.

1. Если - делитель числа, то для того, чтобы число, записанное в-ичной системе счисления, делилось нанеобходимо и достаточно, чтобы наделилась сумма его цифр.

Следствие.Натуральное число, записанное в десятичной системе счисления, делится на 3 (или на 9) тогда и только тогда, когда на 3 (на 9) делится сумма его цифр.

2. Если - делитель числа, то для того, чтобы число, записанное в-ичной системе счисления, делилось нанеобходимо и достаточно, чтобы наделилась разность между суммами цифр этого числа, стоящих на чётных и нечётных местах.

Следствие.Натуральное число, записанное в десятичной системе счисления, делится на 11 тогда и только тогда, когда разность между суммами цифр, стоящих на чётных и нечётных местах в числе, делится на 11.

3. Если - делитель числа, то для того, чтобы число, записанное в-ичной системе счисления, делилось нанеобходимо и достаточно, чтобы наделилось число, записанное последними цифрами числа(взятыми в том же порядке).

Следствие.Натуральное число, записанное в десятичной системе счисления, делится на 2 (или на 5; на 10; на 4; на 25 и т.д.) тогда и только тогда, когда на 2 (на 5; на 10; на 4; на 25 и т.д.) делится последняя цифра числа(последняя цифра; последняя цифра; число, записанное двумя последними цифрами и т.д.).

4. Натуральное число , записанное в десятичной системе счисления, делится на 7 (или на 11; или на 13) тогда и только тогда, когда на 7 (на 11; на 13) делится разность между числом, записанным тремя последними цифрами числа, и числом, записанным остальными цифрами (или наоборот).

Пример 13. Вывести признак делимости на 84 в десятичной системе счисления и выяснить, будет ли число=465252384 делиться на 84.

Заметим, чтоПо предыдущему (частные признаки делимости в десятичной системе счисления) получаем признак делимости на 84 в десятичной системе счисления: числоделится на 84 тогда и только тогда, когда число, записанное двумя последними цифрами числаделится на 4; сумма цифр числаделится на 3 и разность между числом, записанным последними тремя цифрами числаи остальными его цифрами делится на 7.

Проверим, будет ли заданное число делиться на 84. Заметим, что первое условие признака делимости на 84 выполняется: 84⋮4. Сумма цифр числав нашем случае равна 39=4+6+5+2+5+2+3+8+4 - делится на 3. В условии 3 лучше взять разность наоборот: 465252-384=464868. Применим ещё раз данную процедуру: 868-464=404 не делится на 7, т.к. 404=7∙57+5. Поэтому условие 3 признака делимости на 84 не выполняется и число=465252384 не делится на 84.