Question

Найти кол-во натуральных чисел 360 ≤ q ≤ 504 , для которых существуют целые a,b,c такие , что 360a + 504b + qc = 1

Answer 1

Ответ:

48.

Пошаговое объяснение:

Будем использовать как известный следующий факт: уравнение

                                                   ax+by=1

с целыми коэффициентами a  и b имеет решение в целых числах тогда и только тогда, когда a и b взаимно просты, то есть когда наибольший общий делитель (a;b)  этих чисел равен 1. Из этого результата следует, что уравнение

                                                    ax+by=d

с целыми a, b, d  имеет решение в целых числах тогда и только тогда, когда наибольший общий делитель (a;b)  делит d. Переходим к решению задачи.

Заметим, что 360=72·5=2³·3²·5; 504=72·7=2³·3²·7. Если q делится на 2, левая часть уравнения делится на 2, и поэтому решений нет.  Если q делится на 3, левая часть уравнения делится на 3, и поэтому решений нет.

Докажем, что если q не делится ни на 2, ни на 3, уравнение имеет решение. Если кроме того q не делится на 5, то (360;q)=1, поэтому уравнение 360a+qc=1 имеет решение. Остается взять b=0. Если же q не делится на 7, то (504;q)=1, поэтому уравнение 504b+qc=1 имеет решение; остается взять a=0.

Остается случай q=35k, где (k;6)=1. Заметим, что 1=15-14. Рассмотрим два уравнения:

 $360a+35kc_1=15; \ 504b+35kc_2=-14.$

Поскольку (360;35k)=5, причем 5 делит 15, первое уравнение имеет решение.  Поскольку (504;35k)=7, причем 7 делит 14, второе уравнение имеет решение, а тогда уравнение 360a+504b+35kc=1 имеет решение (в качестве c берем $c=c_1+c_2).$ Естественно, мы просто сложили два эти равенства.

Осталось определить, сколько есть чисел между 360 и 504, взаимно простых с 6. Число 360, делящееся на 6, отбрасываем сразу. Остается 144 числа (включая 504); причем 504 делится на 6. Поэтому каждое второе из них делится на 2 (их ровно 144:2=72 штуки), каждое третье делится 3 (их 144:3=48 штук), каждое шестое делится на 6 (их 144:6=24 штуки).

Чисел, взаимно простых с 6, будет 144-72-48+24=48 (последнее слагаемое надо добавить потому, что мы дважды включали числа, делящиеся на 6 - при  подсчете чисел, делящихся на 2, и делящихся на 3).