Question

Разделив некоторое целое число на 15,Боря получил в остатке 8, а разделив его на 20,он получил в остатке 17.Покажи,что Боря ошибся

Answer 1

В первом случае оно заканчивается либо на 0+8=8, либо на 5+8=3(mod10), а во втором на 0+17=7(mod10). Противоречие!

Answer 2

Пусть некоторое целое число, которое разделил Боря на 15 и получил в остатке 8, будет обозначено как n.

Тогда мы можем записать это в виде уравнения: n ≡ 8 (mod 15).

Аналогично, если он разделил это число на 20 и получил в остатке 17, мы можем записать это в виде уравнения: n ≡ 17 (mod 20).

Теперь нам нужно показать, что Боря ошибся в своих вычислениях. Для этого мы можем воспользоваться китайской теоремой об остатках.

Согласно этой теореме, если два уравнения имеют решение, то они имеют единственное решение по модулю, равному произведению модулей.

В данном случае, модули равны 15 и 20, и их произведение равно 300.

Подставим значения остатков в китайскую теорему об остатках:

n ≡ 8 (mod 15) n ≡ 17 (mod 20)

Используем алгоритм расширенного алгоритма Евклида или метод Гаусса для решения системы уравнений.

Итак, пусть n = 15a + 8 и n = 20b + 17, где a и b - целые числа.

Теперь мы можем записать это в виде уравнения: 15a + 8 = 20b + 17.

Раскроем скобки: 15a + 8 = 20b + 17.

Перенесем все константы на одну сторону: 15a - 20b = 17 - 8.

Упростим: 15a - 20b = 9.

Мы видим, что это уравнение не имеет решений. Значит, система уравнений не имеет решений, и Боря действительно ошибся в своих вычислениях.