Однажды, гуляя по парку. Боб и Элен увидели школьный духовой оркестр, готовящийся к параду.

Оркестр был выстроен в колонну по четыре, а один парнишка, несчастный Спиро, замыкал шествие, бредя вне строя. Одинокая фигура, маячившая сзади, по мнению дирижера, портила общее впечатление от оркестра.

Чтобы избавиться от нее, дирижер приказал музыкантам перестроиться в колонну по три, но несчастный Спиро опять остался единственным замыкающим.

Даже когда музыканты разбились на пары, Спиро все равно остался без партнера.

Хотя это было не ее дело, Элен подошла к дирижеру.

Элен. Позвольте мне дать вам один совет?

Дирижер. Мне сейчас не до вас, милая девушка! И без того голова идет кругом.

Элен. Хоть вы и не очень вежливы, я все равно скажу вам, что нужно делать. Перестройте музыкантов в колонну по пять!

Боб. Я как раз собирался предложить то же самое!

Когда оркестр перестроили в колонну по пять, все шеренги оказались заполнены.

Сколько музыкантов было в оркестре?

Как восстановить все число по остаткам

Элен просто пересчитала всех музыкантов в оркестре и обнаружила, что число их кратно 5. Но как можете вы, не видя всего оркестра, определить, сколько в нем музыкантов?

Сделать это можно следующим образом. Пусть N — число музыкантов в оркестре. Мы знаем, что при делении на 2, 3 и 4 оно дает остаток 1 (живым воплощением остатка служит Спиро, в одиночестве марширующий вслед за оркестром). Наименьшее число, обладающее этим свойством, на 1 больше наименьшего общего кратного (НОК) чисел 2, 3 и 4, то есть числа 12. Рассмотрим теперь все числа, кратные 12. Увеличив любое из них на 1, мы получим число, которое при делении на 2, 3 и 4 дает остаток 1.

Когда оркестр перестраивается в колонну по 5, то остаток равен 0. Следовательно, N делится на б без остатка. Решением задачи служат числа, кратные б, которые встречаются в последовательности

13, 25, 37, 49, 61, 73, 85, 97, 109, 121, 133, 145, …

Поскольку число 145 слишком велико для школьного оркестра, то N равно либо 85, либо 25. Имеющаяся у нас информация не позволяет отдать предпочтение какому-нибудь из этих двух чисел.

Хорошим вариантом предыдущей задачи может служить следующая задача. При перестроениях оркестра в колонну по два, три и четыре в последней шеренге каждый раз недостает одного человека, а при построении в колонну по пять все шеренги оказываются заполненными. Сколько музыкантов в оркестре? На этот раз мы должны выписать последовательность чисел, которые на 1 меньше кратных двенадцати и делятся на 5 без остатка: 35, 95, 155, …

Следующий, более трудный вариант задачи принадлежит известному американскому мастеру головоломок Сэму Лойду. По традиции в день св. Патрика члены ирландской общины проводят в Нью-Йорке торжественное шествие. В тот год, о котором рассказывается в новелле Сэма Лойда, Великий маршал ордена св. Патрика безуспешно пытался выстроить участников шествия в колонну по 10, 9, 8, 7, б, 5, 4, 3 и 2 человека, но каждый раз в последней шеренге недоставало одного человека. Суеверные участники шествия решили даже, что среди них незримо витает дух скончавшегося незадолго до дня св. Патрика хромого Кейси, без которого не обходилось ни одно шествие. Вконец отчаявшись, Великий маршал приказал участникам шествия построиться в колонну по одному. Сколько людей приняло участие в шествии, если ирландская община в Нью-Йорке насчитывала в ту пору не более 7000 человек? Задача Сэма Лойда — прекрасный пример на нахождение НОК нескольких чисел. НОК чисел 10, 9, 8, 7, 6, 5, 4, 3 и 2 равно 2520. Вычтя из этого числа скончавшегося от пневмонии хромого Кейси, мы узнаем, что в шествии приняло участие 2519 человек.

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

Старушка несла на базар корзину яиц. Испугавшись пронесшейся мимо лошади, она выронила из рук корзину, и часть яиц разбилась. На вопрос, много ли яиц было в корзине, старушка ответила, что не сильна в арифметике и точное число яиц назвать не может. Правда, потом она все-таки вспомнила, что когда пересчитывала яйца парами, тройками, четверками и пятерками, у нее оставались лишние яйца (1, 2, 3 и 4 соответственно). Сколько яиц старушка несла на базар?

На первый взгляд кажется, что эта задача намного труднее предыдущих. В действительности же она ничем не отличается от первой части нашей рой задача, так как остаток от деления каждый раз на единицу меньше делителя. Решается она таким же способом: нужно найти НОК чисел 2, 3, 4, 5 и вычесть из него единицу.

Задача действительно становится более трудной, если разность между делителем и остатком зависит от делителя. Если у вас есть микрокалькулятор, вы можете на досуге показать своим друзьям забавный фокус.

Фокусник садится в кресло спиной к аудитории. Кто-нибудь из зрителей задумывает любое число не больше 1000, делит задуманное число на 7, 11 и 13, называя каждый раз вслух остаток от деления.

Чтобы не задерживать аудиторию, все вычисления зритель может производить на микрокалькуляторе. Остаток от деления проще всего находить по следующему рецепту: произвести деление, вычесть из полученного частного целую часть, а дробную умножить на делитель, после чего округлить произведение до ближайшего целого числа.

Фокусник, зная лишь три остатка, может отгадать задуманное число. Для этого он достает из кармана свой микрокалькулятор и производит вычисления по следующей «тайной» формуле, которую можно записать на небольшом клочке бумаги и приклеить к передней панели микрокалькулятора:

где a, b и c — остатки от деления задуманного числа на 7, 11 и 13. Задуманное число равно остатку от деления числителя формулы на знаменатель.

Секрет формулы раскрывается просто. Первый коэффициент равен наименьшему кратному произведения bc, которое на единицу больше числа, кратного a. Найти такое число можно по определенным правилам, но когда делители a, b и c не слишком велики,

как в нашем случае, то проще всего действовать прямым подбором: выписать кратные произведения ac (143, 286, 429, 572, 715, …) и найти среди них то, которое при делении на a дает остаток 1. При a = 7 таким кратным является число 715.

Аналогичным образом вычисляются и остальные коэффициенты. Второй коэффициент равен наименьшему кратному произведения ac, которое на единицу больше числа, кратного b, а третий коэффициент равен наименьшему кратному произведения ab, которое на единицу больше числа, кратного c. В знаменателе формулы стоит просто произведение abc. Пользуясь этим алгоритмом, вы можете заготовить «тайную» формулу для любого набора взаимно простых чисел (то есть чисел, не имеющих общих делителей, кроме единицы). Сами числа не обязательно должны быть простыми.

Доказательство формулы для общего случая требует знания так называемой теории вычетов и замечательной теоремы, известной под названием «китайской теоремы об остатках». Она играет важную роль в доказательстве многих нетривиальных теорем теории чисел и решении многих научных проблем.

В качестве упражнения попробуйте вывести «тайную» формулу для упрощенного варианта того же фокуса, восходящего к Сунцзу, китайскому математику, жившему в 1 в., одному из тех ученых, в честь которых теорема об остатках получила название китайской. Задумывать разрешается любое число от 1 до 105. Делить задуманное число следует на 3, 5 и 7. «Тайная» формула оказывается в этом случае столь простой, что после некоторой тренировки вы сможете проделывать все необходимые вычисления «в уме».