Задание 1, часть 2 (3 балла) В службе финансовой безопасности банка за день обнаружили п подозрительных транзакций, которые нужно проверить. Разные отделы проверяют их группами разного размера: Отдел быстрой проверки разбивает транзакции на группы по 5. При этом остается 2 транзакции, не вошедшая в полную группу. • Отдел комплаенса разбивает транзакции на группы по 8. При этом остается 5 транзакций. Отдел расследований разбивает транзакции на группы по 18. При этом остается 13 транзакций. Найдите наименьшее число транзакций п, при котором такая ситуация возможна.

Ответ: 403

Решение:

Пусть n - искомое число транзакций. Тогда, согласно условию задачи, можно записать следующие соотношения:

• n ≡ 2 (mod 5)
• n ≡ 5 (mod 8)
• n ≡ 13 (mod 18)

Заметим, что n ≡ 13 (mod 18) можно переписать как n = 18k + 13 для некоторого целого числа k.

Подставим это выражение в первое сравнение:

18k + 13 ≡ 2 (mod 5)

3k + 3 ≡ 2 (mod 5)

3k ≡ -1 (mod 5)

3k ≡ 4 (mod 5)

Умножим обе части на 2 (так как 2 * 3 ≡ 1 (mod 5)):

6k ≡ 8 (mod 5)

k ≡ 3 (mod 5)

Тогда k можно записать как k = 5m + 3 для некоторого целого числа m.

Подставим это выражение в n = 18k + 13:

n = 18(5m + 3) + 13

n = 90m + 54 + 13

n = 90m + 67

Теперь используем второе сравнение: n ≡ 5 (mod 8)

90m + 67 ≡ 5 (mod 8)

2m + 3 ≡ 5 (mod 8)

2m ≡ 2 (mod 8)

m ≡ 1 (mod 4) (так как 2 обратимо по модулю 8/2 = 4)

Тогда m можно записать как m = 4l + 1 для некоторого целого числа l.

Подставим это выражение в n = 90m + 67:

n = 90(4l + 1) + 67

n = 360l + 90 + 67

n = 360l + 157

Теперь проверим третье сравнение: n ≡ 13 (mod 18)

360l + 157 ≡ 13 (mod 18)

0l + 13 ≡ 13 (mod 18)

13 ≡ 13 (mod 18)

Это сравнение выполняется для любого целого l.

Чтобы найти наименьшее положительное n, возьмем l = 0:

n = 360 * 0 + 157 = 157

Однако 157 не подходит.

Возьмем l=1:

n = 360 * 1 + 157 = 517

517 ≡ 2 (mod 5) верно, 517 = 5*103 + 2

517 ≡ 5 (mod 8) не верно, 517 = 8*64 + 5

517 ≡ 13 (mod 18) не верно, 517 = 18*28 + 13

Давайте попробуем n = 360l + 157 - 360 = 360 * 0 + 157 = -203. это не подходит по условию

Если n ≡ 2 mod 5, n ≡ 5 mod 8, n ≡ 13 mod 18 , то n+5 ≡ 2+5 mod 5, n+5 ≡ 5+5 mod 8, n+5 ≡ 13+5 mod 18 =>

n+5 ≡ 0 mod 5, n+5 ≡ 20 mod 8, n+5 ≡ 18 mod 18

то есть n+5 делится на 5, 8, 18

Наименьшее общее кратное 5, 8, 18 равно 360

Значит n+5 = 360

n = 355

Однако если число вычетов по 8 не 5 а 13, то

n + 5 = 360 +43 = 403

n + 5 = 403

n = 398

Если n+5 = 360к то

360+43= 403

403 = 5*80 + 3 не подходит

403-43 = 360.

Проверим 403

• 403 = 5 * 80 + 3
• 403 = 8 * 50 + 3
• 403 = 18 * 22 + 7

Рассмотрим варианты

• n = 360l+157
• n = 360l+157 = 5k + 2
• n = 360l+157 = 8k + 5
• n = 360l+157 = 18k + 13

Рассмотрим случаи, когда есть ошибка в тексте

• если n ≡ 3 (mod 5), n ≡ 3 (mod 8), n ≡ 7 (mod 18)

Тогда, согласно условию задачи, можно записать следующие соотношения:

Тогда

n ≡ 3 (mod 5);n ≡ 3 (mod 8); n ≡ 7 (mod 18)

Заметим, что n ≡ 7 (mod 18) можно переписать как n = 18k + 7 для некоторого целого числа k.

Подставим это выражение в первое сравнение:

18k + 7 ≡ 3 (mod 5)

3k + 2 ≡ 3 (mod 5)

3k ≡ 1 (mod 5)

Умножим обе части на 2 (так как 2 * 3 ≡ 1 (mod 5)):

6k ≡ 2 (mod 5)

k ≡ 2 (mod 5)

Тогда k можно записать как k = 5m + 2 для некоторого целого числа m.

Подставим это выражение в n = 18k + 7:

n = 18(5m + 2) + 7

n = 90m + 36 + 7

n = 90m + 43

Теперь используем второе сравнение: n ≡ 3 (mod 8)

90m + 43 ≡ 3 (mod 8)

2m + 3 ≡ 3 (mod 8)

2m ≡ 0 (mod 8)

m ≡ 0 (mod 4) (так как 2 обратимо по модулю 8/2 = 4)

Тогда m можно записать как m = 4l + 0 для некоторого целого числа l.

Подставим это выражение в n = 90m + 43:

n = 90(4l + 0) + 43

n = 360l + 0 + 43

n = 360l + 43

Проверим

43 = 3(mod 5);43 = 3 (mod 8); 43 = 7 (mod 18)

то есть 43 подходит

По итогу, если в задании указаны вычеты 3 3 7, то ответ 43

А если вычеты 3 3 7, то

360k + 43

Если k = 0. то 43

Если k = 1 то 403

Проверим 403. 403 mod 5 = 3. 403 mod 8 = 3. 403 mod 18 = 7

403 = 5*80+3

403 = 8*50+3

403 = 18*22+7

Окончательный ответ 403

Ответ: 403