Будем использовать как известный следующий факт: уравнение
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. Рассмотрим два уравнения:
[tex]360a+35kc_1=15; \ 504b+35kc_2=-14.[/tex]
Поскольку (360;35k)=5, причем 5 делит 15, первое уравнение имеет решение. Поскольку (504;35k)=7, причем 7 делит 14, второе уравнение имеет решение, а тогда уравнение 360a+504b+35kc=1 имеет решение (в качестве c берем [tex]c=c_1+c_2).[/tex] Естественно, мы просто сложили два эти равенства.
Осталось определить, сколько есть чисел между 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).
Answers & Comments
Verified answer
Ответ:
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. Рассмотрим два уравнения:
[tex]360a+35kc_1=15; \ 504b+35kc_2=-14.[/tex]
Поскольку (360;35k)=5, причем 5 делит 15, первое уравнение имеет решение. Поскольку (504;35k)=7, причем 7 делит 14, второе уравнение имеет решение, а тогда уравнение 360a+504b+35kc=1 имеет решение (в качестве c берем [tex]c=c_1+c_2).[/tex] Естественно, мы просто сложили два эти равенства.
Осталось определить, сколько есть чисел между 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).