Решение задачи о взвешивании

Решение задачи о взвешивании

Итак, нам нужно решить в целых числах уравнение (2). Определяем неизвестное х:

Им-то мы и воспользуемся. Ведь наша цель — уменьшить коэффициент при неизвестном. Вве­дем обозначение:

Задача сведена к ре­шению в целых числах уравнения 3x1y=1. Решая это уравнение, получим y=3х1-1, где х1— любое целое число.

А тогда

х=9-2•(3x1-1)+x1= 11-5х1Таким образом, общее решение уравнения (2) можно записать так:

Найдем несколько решений этого уравнения:

Уравнение (2) имеет бесконечное множество решений, но мы сможем воспользоваться толь­ко некоторыми. Это зависит от числа гирь в нашем распоряжении, да и размеров чаш.

Мы рассмотрели два уравнения первой сте­пени. Каждое из них, как удалось установить, имеет целочисленные решения. Однако наряду с ними можно указать уравнения, которые решений в целых числах не имеют.

Таково, например, уравнение

 

В самом деле, допустив, что при некоторых целых х и у равенство (11) верно, мы получим, что 5 делится на 3.

Какие неопределенные уравнения разреши­мы в целых числах?

Можно ли для всякого разрешимого в це­лых числах неопределенного уравнения первой степени найти его решение методом рассеивания?

На первый вопрос отвечает теорема:

Уравнение с целыми коэффициентами а1,

а2, …,аnb:

а1х1 а2x2+…+аnxn=b (12)

разрешимо в целых числах только в том случае, если свободный член b делится на наибольший общий делитель чисел а1, а2, …, аn.

Ответим на другой вопрос: всегда ли пред­ложенный метод решения в целых числах неопределенных уравнений первой степени приво­дит к цели?

Если а1— наименьший по абсолютной вели­чине коэффициент при неизвестном в уравнении (12), то мы заменяем это уравнение другим, в котором все коэффициенты, кроме коэффициента a1, заменены остатками от деления этих чи­сел на а1Если хотя бы один из коэффициен­тов а2а3, …, аn не делится на а1, то полу­чим уравнение, коэффициенты которого по аб­солютной величине меньше, чем у данного. С этим уравнением поступаем так же, как сдан­ным. Если все числа а2а3, …, аn делятся на a1 а b не делится, то данное уравнение нераз­решимо. Если все числа a2а3…, аn и b делят­ся на а1, то, деля обе части уравнения на а1, получим уравнение, целые решения которого находятся без труда.

Из этого рассуждения следует, что описан­ный метод позволяет найти целые решения вся­кого разрешимого в целых числах неопределен­ного уравнения с целыми коэффициентами.

Print Friendly, PDF & Email