Иэн Стюарт - Математические головоломки профессора Стюарта

0 1 4 9 6 5 6 9 4 1

и приведенный выше список правил для определения последней цифры квадрата по последней цифре числа – это всего лишь другой способ сказать то же самое.

За исключением начального 0, список квадратов (по модулю 10) симметричен: числа 1, 4, 9, 6 после 5 повторяются в обратном порядке: 6, 9, 4, 1. Симметрия возникает благодаря тому, что квадраты n и 10 – n по модулю 10 равны. В самом деле, 10 – n – то же, что – n (mod 10), а n ² = (− n )². Поэтому данные четыре числа в списке фигурируют дважды ; 0 и 5 встречаются там только по одному разу, а 2, 3, 7, 8 не встречаются вовсе. Это не слишком демократично, но это так.

Что происходит, если мы берем другой модуль? Величины квадратов по этому модулю называются квадратичными вычетами . (Здесь под «вычетом» подразумевается остаток от деления на модуль.) Остальные цифры при этом становятся квадратичными невычетами .

Предположим, к примеру, что модуль равен 11. Тогда возможные полные квадраты (чисел, меньших 11) равны

0 1 4 9 16 25 36 49 64 81 100.

По модулю 11 это дает

0 1 4 9 5 3 3 5 9 4 1.

Таким образом, квадратичные вычеты (по модулю 11) – это

0 1 3 4 5 9.

А невычеты – это

2 6 7 8.

Приведем небольшую таблицу.

На первый взгляд, никаких особенных закономерностей, кроме уже упомянутых, не заметно. На самом деле этим отчасти и интересна данная область математики: хотя шаблоны существуют, отыскать их непросто. Многие величайшие математики, в том числе Эйлер и Карл Фридрих Гаусс, уделяли внимание этой области.

Возводя число в квадрат, мы умножаем его на самого себя, а там, где речь заходит об умножении, в теории чисел главную роль всегда играют простые числа. Поэтому стоит начать с простых модулей – 2, 3, 5, 7, 11 – в приведенном списке. Модуль 2 уникален: единственные возможные вычеты по модулю 2 – это 0 и 1, и оба они являются полными квадратами. Для всех остальных простых чисел примерно половина вычетов являются квадратами, а остальные – не являются. Точнее, если p – простое число, то существует ( p + 1)/2 различных квадратичных вычетов и ( p − 1 )/2 невычетов. Квадратичные вычеты обычно являются квадратами двух различных чисел, n ² и (– n )² для подходящего n . Однако 0 встречается в списке лишь однажды, потому что –0 = 0.

Составные модули усложняют ситуацию. Теперь одни и те же вычеты иногда могут быть квадратами больше чем двух чисел. К примеру, 1 по модулю 8 встречается четыре раза, как квадрат 1, 3, 5 и 7. Лучший способ разобраться во всем этом – воспользоваться современной абстрактной алгеброй, но имеет смысл взглянуть и на модуль 15. У него два простых множителя: 3 × 5. А вот список квадратов:

Таким образом, квадратичные вычеты по модулю 15 равны

0 = 0²

1 = 1², 4², 11², 14²

4 = 2², 7², 8², 13²

6 = 6², 9²

9 = 3², 12²

10 = 5², 10²

Некоторые вычеты возникают один раз, некоторые дважды, некоторые четырежды. Те, которые встречаются в списке меньше четырех раз, являются квадратами чисел, кратных либо 3, либо 5, то есть простым множителям 15. Все остальные числа возникают группами по четыре, где квадраты всех четырех равны.

Это общая закономерность для любого модуля вида pq , где p и q – различные нечетные простые числа. Числа от 0 до pq – 1, не кратные ни p , ни q , разделяются на четверки с равными квадратами. (Это не работает, если одно из простых чисел равно 2: к примеру, 10 = 2 × 5, но мы уже видели, что в этом случае квадраты либо одиноки, либо стоят парами.)

В алгебре мы привыкаем к мысли, что у каждого положительного числа имеется два квадратных корня: один положительный, другой отрицательный. Но в арифметике по модулю pq большая часть чисел (те, что не делятся ни на p , ни на q ) имеет по четыре различных квадратных корня.

Этот любопытный факт имеет замечательное приложение, к которому мы и перейдем.

Предположим, что Алиса и Боб хотят сыграть в бросание монетки с вероятностью того или иного результата 50:50. Как мы уже знаем, Алиса находится в Алис-Спрингс, а Боб – в Боббингтоне. Могут ли они бросать монетку по телефону? Главная загвоздка – та же, что при игре в покер. Если бросает монетку (или проделывает любую другую операцию с равновероятным исходом) Алиса и она же сообщает результат Бобу, то тот никак не может быть уверен, что она говорит правду. Конечно, в наше время они могли бы делать это во время общения по скайпу и наблюдать за бросанием монетки, но даже в этом случае результат можно подделать, сняв заранее несколько бросков и показав собеседнику запись вместо онлайн-трансляции.