Найти остаток от деления на 6

[larkova_alina]

Число $a$ дает остаток 2 при делении на 3 и остаток 1 при делении на 4. Найдите остаток от деления $a$ на 6.

$a=3b_1+2,$
$a=4b_2+1,$
$a=6b_3+r_3$, $r_3=?$.

Что делать?
Если сложить первое и второе уравнение, то получим $2a=3(b_1+1)+4b_2.$
Отсюда видно, что $a$-нечетное. Поэтому $r_3$-нечетное.
То есть, $r_3=1 \vee r_3=3 \vee r_3=5.$ Как дальше?

[Someone]

Умножьте на что-нибудь первое и второе равенство и вычтите, чтобы получить равенство $a=k\cdot\ldots+r$, где $k$ делится на $6$.

[Joker_vD]

Или в лоб проверить, какой из трех вариантов верный

[larkova_alina]

Someone в сообщении #678194 писал(а):

Умножьте на что-нибудь первое и второе равенство и вычтите, чтобы получить равенство $a=k\cdot\ldots+r$, где $k$ делится на $6$.

$4a=12b_1+8,$
$3a=12b_2+3,$
$a=12(b_1-b_2)+5=6\cdot 2(b_1-b_2)+5,$
$r_3=5.$
Спасибо за подсказку.

-- 31.01.2013, 11:12 --

Joker_vD в сообщении #678195 писал(а):

Или в лоб проверить, какой из трех вариантов верный

А как в лоб проверить?

[Joker_vD]

$6k+1$ при делении на три дает в остатке $1$, а не три.
$6k+3$ при делении на три вообще в остатке дает ноль.
А вот $6k+5$...

-- Чт янв 31, 2013 11:45:27 --

Причем можно и не таскать за собой эти $6k$, а проверить просто $1,3,5$ — какие у них остатки при делении на три, четыре и шесть.

[Sonic86]

larkova_alina, на будущее можете иметь ввиду, что эта задача - на китайскую теорему об остатках. В статье есть и алгоритмы нахождения решений.