6.8. Общее решение Пусть пара чисел x = x0, y = y0 удовлетворяет уравнению
ax + by = c
в целых числах с взаимно простыми коэффициентами а и b. Докажите, что формулы
x = x0 + bk, y = y0 + ak
с целым параметром k задают все решения этого уравнения,
6.9. Сколько нужно мешков? Для перевозки зерна имеются мешки, в которые входит либо 60 кг, либо 80 кг зерна. Сколько надо заготовить тех и других мешков для загрузки 1 т зерна таким образом, чтобы все мешки были полными? Какое наименьшее количество мешков при этом может понадобиться?
6.10. Сколько нужно банок? Требуется разлить 20,5 литра сока в банки по 0,7 л и 0,9 л так, чтобы все банки оказались полными. Сколько каких банок надо заготовить? Какое наименьшее количество банок при этом может понадобиться?
6.11. Частное решение Докажите, что уравнение
ax + by = c
с взаимно простыми коэффициентами а и b имеет решение
где 
- предпоследняя подходящая дробь к цепной дроби, в которую раскладывается дробь a/b (см. задачи 5.7, 5.10, 5.12).
6.12. Загрузка трехтонок Для перевозки большого количества контейнеров по 170 кг и по 190 кг выделены трехтонные машины. Можно ли ими загружать машины полностью?
6.13. Целые точки на прямой Сколько точек с целочисленными координатами, удовлетворяющими неравенствам х<0 и y>0, лежит на прямой
8x - 13y + 11 = 0?
6.14. Наименьшим числом У продавца имеются 100-граммовые гирьки и консервные банки весом по 450 г. Как с их помощью отвесить на чашечных весах 2,5 кг сахарного песка за один раз, используя для взвешивания наименьшее количество гирек и банок в общей сложности?
Решения
6.1. Пусть нужно уплатить денежную сумму в n рублей. Если число n делится на 3, то эту сумму можно уплатить одними трехрублевыми купюрами. Если остаток от деления числа n>7 на 3 равен 1, то
причем 3q + 1>7, откуда q>2 и, значит, в этом случае сумму можно уплатить q-3 трехрублевыми купюрами и двумя пятирублевыми. Если же остаток от деления числа n>7 на 3 равен 2, то
причем 3q + 2>7, откуда q>1 и, значит, в этом случае сумму можно уплатить q-1 трехрублевыми купюрами и 1 пятирублевой.
6.2. Если у кассира нет ни одной пятирублевой купюры, то покупатель может заплатить за покупку стоимостью в n рублей только при условии, что число n кратно 3. Если у кассира есть 1 пятирублевая купюра, то. покупатель может заплатить за покупку только при условии, что число n либо кратно 3, либо дает остаток 1 при делении на 3 (в последнем случае покупатель платит на 5 рублей больше и получает 5 рублей сдачи: n = 3q + 1 = 3(q + 2) - 5). Наконец, если кассир имеет 2 пятирублевые купюры, то покупатель может заплатить за покупку при любом значении n (в случае, когда остаток от деления числа n на 3 равен 2, покупатель может заплатить на 10 рублей больше и получить 10 рублей сдачи:
Таким образом, в условиях задачи кассир должен иметь минимум 2 пятирублевые купюры.
6.3. Пусть (a, b) = d и число с не делится на d. Тогда если уравнение ax + by = c имеет целочисленное решение x = x0, y = y0, то справедливо числовое равенство ax0 + by0 = c, в котором левая часть делится на d (ибо числа а и b кратны d), а правая нет. Полученное противоречие доказывает, что указанное уравнение в целых числах не может иметь решений.
6.4. Если сумму в 1000 рублей можно набрать с помощью х, y и z купюр достоинством в 1 рубль, 10 рублей и 100 рублей соответственно, то справедливо равенство x + 10y + 100z = 1000. Если к тому же всего купюр должно быть x + y + z = 40, то целые числа x и y должны удовлетворять уравнению (40 - y - z) + 10y + 100z = 1000, или 9y + 99z = 960. Согласно утверждению задачи 6.3, последнее уравнение в целых числах не имеет решений, так как число 960 не делится на наибольший общий делитель пары чисел 9 и 99, равный 9.
6.5. Задача сводится к решению уравнения
в целых неотрицательных числах. Заметим, что число y не может быть равным 0, так как иначе уравнение