p-адические числа для «чайников»

0. Предисловие

В математике существуют весьма интересные сущности под названием «p-адические числа». По сути ничего сложного в них нет. Однако в учебниках и энциклопедиях они вводятся таким образом, что непосвящёному очень трудно понять, о чём идёт речь.

В данной статье сделана попытка объяснить p-адические числа «для чайников».

Для начала вводятся новые математические объекты, условно названные «квазибесконечными числами» и описываются некоторые их свойства. А затем показывается, как от них перейти к p-адическим числам.

1. Определение.

«Квазибесконечным числом» (КБЧ) называется бесконечная последовательность цифр (из какой-либо системы счисления, например десятичной), идущая справа налево.

Пример: ...3819248393684028831439284578

Эти числа названы «квазибесконечными», потому что они кажутся бесконечными, но на самом деле не являются таковыми.

2. Арифметические операции.

Сумма двух КБЧ вычисляется справа налево по обычному методу сложения столбиком (вычисляется сумма двух цифр очередного разряда, прибавляется единица при наличии переноса из предыдущего разряда, затем определяется цифра суммы данного разряда и наличие переноса в следующий разряд). [В нижеприведённых таблицах наличие переноса обозначается чертой над соответствующей цифрой.] Например:

+ ...204591038205
...436103493293
...640694531498

Аналогично вычисляется разность двух КБЧ (только вместо переноса здесь заимствование из следующего разряда).

...204591038205
...436103493293
...768487544912

Умножение также вычисляется по обычном методу умножения столбиком, как сумма бесконечного ряда слагаемых.

×... 204591038205
... 436103493293
... 613773114615
... 841319343845
... 409182076410
... 613773114615
... 841319343845
... 818364152820
... 613773114615
... 000000000000
... 204591038205
... 227546229230
... 613773114615
... 818364152820
············
... 672123259065

Деление осуществляется подбором цифр справа налево, используя тот факт, что для вычисления n последних (правых) цифр произведения достаточно перемножить числа, образованные n последними цифрами сомножителей. (Деление выполняется проще, если основание системы счисления — простое число, иначе возникают неоднозначности в подборе цифр.)

3. Целые числа.

Рассмотрим те КБЧ, в которых влево от некоторой позиции идут одни нули, например:

...000000, ...000001, ...000002, ...001936, ...

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

4. Целые отрицательные числа.

Попробуем вычесть из нуля (...00000) единицу (...00001). Формально следуя алгоритму вычитания столбиком с заимствованием из следующего разряда, мы получим ...99999. Снова вычитая единицу, мы получим ...99998, ...99997 и т. д. Нетрудно заметить, что это обычный дополнительный код, широко используемый в компьютерах для представления отрицательных чисел (хотя в компьютерах обычно используется двоичная система, а не десятичная).

Таким образом, чтобы получить −x (т. е. число, которое при сложении с x даёт ...00000), нужно:

1) Каждую цифру xi заменить на (N−1)−xi (где N — основание системы счисления)

2) К получившемуся числу прибавить ...00001.

Например, в десятичной системе:

−...000000023 = ...999999977

В двоичной системе:

−...000000101 = ...111111011

Таким образом, те КБЧ, в которых влево от некоторой позиции идут одни только наибольшие цифры данной системы счисления, можно отождествить с обычными отрицательными целыми числами.

5. Дроби.

Рассмотрим число ...11111 (состоящее из одних единиц). Нетрудно заметить, что ...11111 × ...00009 = ...99999 (т. е. −1). Поэтому можно считать, что ...11111 = −1/9. Дополнение к ...11111 (т. е. ...88889) будет равно +1/9.

Естественно предположить, что всякое периодическое КБЧ (т. е. такое, в котором слева от некоторого разряда идёт бесконечно повторяющаяся последовательность цифр) представляет некоторую дробь (т. е. при умножении периодического КБЧ на некоторое конечное число можно получить конечное число).

Теорема. Если основание системы счисления N — простое число, то для любого числа x, не кончающегося на 0, существует обратное число x−1 (т. е. такое, что x · x−1=1).

Доказательство. Докажем, что мы сможем подобрать последнюю цифру числа x−1, а затем по очереди все остальные, так, чтобы последняя цифра произведения была 1, а все остальные 0.

Пусть x0 — последняя цифра числа x; подберём y0 — последнюю цифру числа x−1. Поскольку основание системы счисления N — простое число, то при вычислениях по модулю N для любого x0 (≠0) мы можем найти такое y0, что x0 · y0 = 1.

Далее, исходя из алгоритма умножения столбиком, для очередной цифры xi мы подберём цифру yi по уравнению

x0 · yi + xi · y0 + C = 0

(вычисления осуществляются по модулю N; C — «довесок», образующийся от перемножения предыдущих цифр).

Поскольку x0 ≠ 0, то это уравнение всегда разрешимо. Теорема доказана.

Следствие. Если основание системы счисления — простое число, то можно делить (без остатка) на любое число, не кончающееся на 0.

Примеры дробей (повторяющаяся последовательность цифр заключена в скобки).

В десятичной системе:

1/3 = ...(6)7

1/7 = ...(285714)3

1/11 = ...(09)1

В троичной системе:

1/2 = ...(1)2

1/11 = ...(02)1

1/12 = ...(1210)2

В двоичной системе:

1/11 = ...(01)1

1/101 = ...(0110)1

1/111 = ...(011)1

6. Неэквивалентность разных систем счисления.

В десятичной системе можно представить 1/3 (как ...66667), но нельзя представить 1/2 — поскольку при умножении на 2 последняя цифра всегда получается чётной, а у нас должна получиться единица. В троичной системе, наоборот, можно представить 1/2 (как ...11112), но нельзя представить 1/3 (при умножении на 3 = 103 последняя цифра всегда получается равной 0, а должна получиться единица).

Таким образом, можно заметить, что в данной системе счисления можно представить в виде КБЧ только те (несократимые) дроби, у которых знаменатель является взаимно простым с основанием системы счисления. Поэтому КБЧ, записанные в одной системе счисления, могут не иметь никакого соответствия в другой системе счисления.

7. Квадратные корни.

Пример. В десятичной системе нетрудно извлечь квадратный корень из ...00004 — это будут ...00002 и ...99998 (понятно, что квадратные корни всегда появляются парами).

Теорема. Если основание системы счисления N — простое число, большее 2, то для любого числа x, не кончающегося на 0, существует квадратный корень √x, при условии, что существует число y0, которое при возведении в квадрат по модулю N даёт число, равное последней цифре x.

Доказательство. Последняя цифра корня y0 известна из условия. Подберём очередную цифру корня yi.

Исходя из алгоритма умножения столбиком

2 · yi · y0 + C = xi

(вычисления осуществляются по модулю N, xi — очередная цифра исходного числа; C — «довесок», образующийся от перемножения предыдущих цифр).

Поскольку y0 ≠ 0, а N — простое число, большее 2, то это уравнение всегда разрешимо. Теорема доказана.

Пример 1. В 7-ричной системе счисления √2 = ...266421216213 и ...400245450454 (здесь уже нельзя определить, какой корень положительный, а какой отрицательный).

Пример 2. В 7-ричной системе счисления нельзя записать √3, поскольку никакое целое число при возведении в квадрат по модулю 7 не даёт 3 (т. е. нельзя подобрать последнюю цифру).

Пример 3. В 11-ричной системе счисления √3 = ...761192486 и ...349918625.

8. Комплексные числа.

В некоторых системах счисления можно вычислить корень из −1 (в тех системах, где одна из цифр при возведении в квадрат по модулю N (основание системы счисления) даёт N−1 (т. е наибольшую цифру)).

Пример 1. В 5-ричной системе счисления √−1 = ...412013233 и ...032431212 (при возведении в квадрат они дают ...444444444, т. е. −1; определить, какое из этих двух чисел равно i, а какое −i, невозможно).

Пример 2. В 7-ричной системе счисления нельзя записать √−1, поскольку никакое целое число при возведении в квадрат по модулю 7 не даёт 6 (т. е. нельзя подобрать последнюю цифру).

Пример 3. В 7-ричной системе счисления √−3 = ...20155410615 и ...46511256052 (при возведении в квадрат они дают ...66666666664, т. е. −3).

Пример 4. В 13-ричной системе счисления √−1 = ...101550155 и ...BCB77CB78 (при возведении в квадрат они дают ...CCCCCCCCC, т. е. −1).

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

9. Вычислимые КБЧ.

Вычислимым КБЧ назовём такое, для которого существует алгоритм, выдающий по порядку (справа налево) все цифры данного КБЧ (в заданной системе счисления). Хотя общее количество КБЧ несчётное, количество вычислимых КБЧ счётное (поскольку мы считаем, что алгоритм — это некий конечный текст в конечном (или счётном) алфавите, а количество таких текстов — не более чем счётное).

Понятно, что все конечные и периодические КБЧ являются вычислимыми.

Сумма, разность и произведение двух вычислимых чисел также являются вычислимыми (поскольку они вычисляются справа налево, а после вычисления очередной цифры к ней уже не приходится возвращаться).

Если основание системы счисления — простое число, то деление вычислимых чисел и извлечение квадратного корня из вычислимого числа также являются вычислимыми числами. (Возможно, что эти операции являются вычислимыми для любой системы счисления, но это надо доказать.)

Преобразование в другую систему счисления иногда является вычислимым, иногда нет.

10. КБЧ с дробной частью.

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

1/5 = ...00000.2

1/300 = ...666666.67

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

11. Модуль квазибесконечного числа

Определим модуль a квазибесконечного числа a в системе счисления по основанию N следующим образом:

Модуль обладает обычными свойствами модуля, например:

a+b a + b

Если N — простое число, то верно и

a · b = a · b

Но есть и необычные свойства, например, если а≠b, то

a+b = max (a, b) и

a+b = a−b

Если N — составное число, то

a · b a · b

12. p-адические числа

Теперь можно объяснить, что такое p-адические числа. Они почти не отличаются от вышеописанных КБЧ, однако имеют следующие особенности:

Сайт создан в системе uCoz