Question

Известно, что число a при делении на 5 дает остаток 2, а при делении на 3 — остаток 1. Найдите остаток от деления числа a на 15.

Answer 1

Числа, которые при делении на 5 дают остаток 1: 6;11;16;21;26;31;36;41;46;....
Числа, которые при делении на 3 дают остаток 2: 5; 11;14;17;20;23;26;29;32;35;38;41;44;48;...
Среди них общие: 26 и 41. Они при делении на 15 дают остаток 11.

Answer 2

Для решения этой задачи мы можем воспользоваться китайской теоремой об остатках. По этой теореме, если известны остатки числа a при делении на два взаимно простых числа, то можно однозначно определить остаток числа a при делении на их произведение.

В данном случае, мы знаем, что a имеет остатки 2 при делении на 5 и 1 при делении на 3. 5 и 3 взаимно просты, поэтому мы можем использовать китайскую теорему об остатках, чтобы найти остаток числа a при делении на 15.

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

a ≡ 2 (mod 5) a ≡ 1 (mod 3)

Найдем сначала решение для первого уравнения. Для этого мы можем перебирать числа вида 5n + 2, пока не найдем такое, которое подходит. Несложно заметить, что при n = 1 получится число 7, которое подходит:

7 ≡ 2 (mod 5)

Теперь найдем решение для второго уравнения. Аналогично, мы можем перебирать числа вида 3m + 1. При m = 1 получаем число 4:

4 ≡ 1 (mod 3)

Таким образом, мы получили решения для обоих уравнений:

a ≡ 7 (mod 5) a ≡ 4 (mod 3)

Теперь мы можем применить общую формулу для решения системы уравнений с двумя уравнениями и двумя неизвестными. Эта формула имеет вид:

a ≡ a1 * N2 * y2 + a2 * N1 * y1 (mod N1 * N2),

где a1 и a2 - решения уравнений, N1 и N2 - числа, при которых берутся остатки, а y1 и y2 - числа, обратные к N1 по модулю N2 и к N2 по модулю N1 соответственно.

В нашем случае, N1 = 5, N2 = 3, a1 = 7, a2 = 4. Найдем сначала обратный элемент y1 по модулю N2 = 3. Так как 5 и 3 взаимно просты, то у1 ≡ 2 (mod 3). Найдем теперь обратный элемент y2 по модулю N1 = 5. Так как 3 и 5 взаимно просты, то y2 ≡ 1 (mod 5).

Теперь мы можем подставить все значения в формулу:

a ≡ 7 * 3 * 2 + 4 *