Материал для подготовки к разделу "Арифметика вычетов"

1. Арифметика вычетов

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

(1)

где для некоторого целого .

Иногда называют вычетом по модулю , – конгруэнтным по модулю .

Формулу (1) также можно интерпретировать следующим образом: если два числа имеют одинаковые остатки от деления на , то они сравнимы по модулю (например, ).

В отличие от (1) операция означает остаток от деления (например, ). Эта операция называется приведением по модулю.

Далее приведены свойства функции сравнения:

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

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

3. К любой части сравнения можно прибавить любое число, кратное модулю: .

4. Сравнения по одинаковому модулю можно почленно перемножать: ,.

5. Обе части сравнения можно возвести в одну и ту же степень.

6. Как следствие из вышеперечисленных свойств, получаем: ,,…,,

7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.

8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.

9. Если сравнение имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

10. Если сравнение имеет место по модулю , то оно имеет место и по модулю , равному любому делителю числа .

11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.

12. К обеим частям сравнения можно прибавить одно и тоже число; обе части сравнения можно умножить на одно и тоже число.

Свойство операции приведения по модулю:

, где.

Пример 1.

Проверим 7-ое свойство функции сравнения: , общие делители 24 и 6 – 2,3. Взаимно простое с 9 – это 2: . Тогда делим на 2 обе части сравнения: , иначе было бы неверно: .

Пример 2.

Проверим свойство операции приведения:

Пример

Найдем при помощи свойства операции приведения по модулю:

Такой прием называется цепочкой разложения, в основе которой лежит двоичное представление числа.

Числа, сравнимые по модулю , образуют класс вычетов по модулю . Все числа из одного и того же класса имеют один и тот же остаток от деления на . Любое число из класса вычетов называется вычетом по модулю .

Всего имеется классов вычетов по модулю (если классы обозначать как ): .

Свойства классов вычетов:

1. .

2. .

3. Любые чисел попарно не сравнимые по модулю образуют полную систему вычетов.

4. Если и «пробегает» полную систему вычетов по модулю , то , где – любое число, также пробегает полную систему вычетов по модулю .

Полная система вычетов – это совокупность вычетов, взятых по одному из каждого класса эквивалентности.

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

Пример 3.

Рис. 1. Иллюстрация к образованию классов вычетов по модулю 8

На рис. 1 изображен процесс «наматывания» цепочки целых чисел на колечко с делениями, при этом на одно деление автоматически попадают сравнимые между собой числа.

Существуют 8 классов вычетов по модулю . В каждом классе находятся числа, дающие при делении на одинаковые остатки:

0,8,16,

…

1,9,17,

…

2,10,15,

…

3,11,19,

…

4,12,20,

…

5,13,21,

…

6,14,22,

…

7,15,23,

…

Название класса

Например, одна из полных систем вычетов по модулю 8: 1200, 33, 42, 3, 12, 629, 22, 807.

Приведенная система вычетов: 0, 1, 3, 5, 7.

Количество классов вычетов в приведенной системе вычетов минус один обозначают как и называют функцией Эйлера (или представляет собой количество чисел ряда взаимно простых с ). Например, , , , , , , . Кроме того,

Свойства функции Эйлера:

1. Если – простое, то .

2. Если – простое, то .

3. Мультипликативность функции Эйлера: если .

Следствие из этого свойства: .

Пример 4.

Дано . Найдем простые все числа , на которые делится без остатка: 3, 5. Тогда . Посчитаем для проверки количество классов в приведенной системе вычетов: 1, 2, 4, 7, 8, 11, 13, 14. Оно равно 8.

Теорема Эйлера. Пусть , , – функция Эйлера. Тогда: .

Например, , .

Теорема Ферма (малая теорема Ферма или малая теорема Эйлера). Если , – простое, то

Следствие из теоремы Ферма: , где не обязательно , но – простое.

Пример 5.

Девятая степень однозначного числа оканчивается цифрой . Найти это число.

. Понятно, что , , .

По теореме Эйлера: , возведем в квадрат обе части сравнения: . Почленно поделим на : .

Пример 6.

Доказать, что .

. – простое. По теореме Ферма: , где . Получаем систем:

Возводим каждое сравнение почленно в третью степень и складываем: .

Пример 7.

Найти остаток от деления на .

– простое, по теореме Ферма . Возведем данное сравнение в 4-ую степень и умножим на : остаток равен .

Пример 8.

Найти две последние цифры числа .

Две последние цифры числа – это остаток от деления на 100.

, значит:

. Так как , по теореме Эйлера . , 2 и 5 простые числа, значит: . Тогда: ; возведем в 100 степень и умножим на : .

Значит, последние две цифры 4 и 9.

Пример 9.

Показать, что делится на 105.

Решение.

, . По теореме Ферма:

.

Умножим эти сравнения и вычтем : .

Пример 10.

Найти вычет числа по .

Разделим степень на с остатком ; . По теореме Ферма (так как – простое): .

Тогда . Значит, .

Рассмотрим сравнение:

(2)

Под решением любого сравнения понимается класс вычетов по модулю , один элемент которого (а значит и все) удовлетворяют данному сравнению. Решить сравнение – значит найти все , которые удовлетворяют данному сравнению, при этом весь класс вычетов по модулю считается за одно решение.

Пример 11.

Сравнение 5-ой степени: .

Класс вычетов для :. Данному сравнению удовлетворяют: , так как и . Таким образом у данного сравнения есть два решения: и .

Естественно, метод перебора затруднителен. В случае сравнения первой степени если решение означает отыскание целых таких, что: , то есть . – это обратный к по модулю элемент.

Умножим (2) на : . С учетом получаем:. (3)

Значит, сравнение первой степени имеет одно решение по модулю .

Если же , то для решения сравнения (2) необходимо, чтобы делил без остатка. При этом сравнение будет иметь решений: .

Пример 12.

Решить сравнение .

. Поэтому по свойству 11,7,8 функции сравнение: . Далее для решения сравнения можно использовать два подхода:

1. Алгоритм Евклида (применяется при небольших для нахождения : ).

2. Способ Эйлера.

Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя .

Выполним следующие деления с остатком:

Тогда . То есть равен последнему отличному от нуля остатку в алгоритме Евклида.

Пример 13.

Найдем .

Решение.

Значит, .

Если мы хотим найти линейное разложение НОД’а: , то надо остатки выражать друг через друга:

Пример 14.

Решим сравнение .

.

Найдем линейное разложение НОД’а: :

Значит, . По формуле (3): . Проверим, действительно ли так:

Пример 15.

Решим сравнение .

Решение.

. Получаем: . Найдем линейное разложение НОД’а: :

Значит, .

Получается, что .

Исходное решение:

Теорема 1.

Пусть , . Тогда сравнение (2) имеет решение (3), где .

Пример 16.

Решить сравнение .

, .

Значит: .

Отрицательным моментом этого метода является то, что необходимо возводить в степень.

Число , взаимно простое с модулем (), принадлежит показателю , если такое наименьшее натуральное число, что выполняется сравнение: .

Свойства данного числа :

1. Числа попарно не сравнимы по модулю .

2. .

3. делит без остатка.

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

4. По любому простому модулю существует первообразный корень.

5. Пусть , – различные простые делители числа . Число , взаимно простое с модулем , будет первообразным корнем тогда и только тогда, когда не выполнено ни одно из следующих сравнений: , ,…, .

Теорема. Если – нечетное простое число, то по модулям вида и () существуют первообразные корни.

Пример 17.

, . Простые делители : 2 и 3. Значит, первообразный корень не должен удовлетворять сравнениям: и . Числа, взаимно простые с : .

Проверим их:

Значит, первообразными корнями по модулю являются 3 и 5.

Проверим выполнение сравнения: . , – верно.

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

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

Пусть - некоторое простое число. Последовательность целых чисел =, обладающих тем свойством, что для всех n, определяет новый объект,называемый целым -адическим числом.

Сложение и умножение целых p-адических чисел определяется как почленное сложение и умножение таких последовательностей. Для них непосредственно проверяются все аксиомы кольца. Кольцо целых p-адических чисел обычно обозначается .

Итак, рассмотрим сравнение: по степеням простого числа 7. При n=1 сравнение имеет два решения:

Положим теперь n=2. Из cледует так что решение сравнения второго надо искать в виде ,где - одно из чисел, определяемых сравнением первым. Теперь найдем решения вида . (при это решения рассматриваются так же).Подставляем это выражение для во второе сравнение, получаем:

9+6*+

1+6,

.

Таким образом, получаем решение

Аналогично при n=3 получаем и из сравнения

находим т.е.

Этот процесс мы можем продолжать бесконечно.

Мы получим последовательность

Она обладает свойствами:

,

,

.

Итак, процесс построения последовательности

,

,

.

Чем-то напоминает процесс извлечения квадратного корня из 2.

Например: .

В нашем случае строится последовательность целых чисел ,для которых

Делится на . Такакя аналогия становится более отчетливой,если условиться два целых числа называть близкими (точнее -близкими, где – некоторое простое число), когда их разность делится на достаточно большую степень Тогда можно сказать, что квадраты чисел последовательности

,

,

.

При возрастании n становится сколь угодно 7-близкими к 2.

Задание последовательности определяет вещественное число .

Можно предположить, что наша последовательность так же определяет число a некоторой новой природы, причем такое, что =2.

Если же последовательность рациональных чисел такова, что при всех n,то ее пределом так же будет . Все это приводит нас к определению. Две последовательности и тогда и только тогда определяютодно и то же целое -адическое число, когда, для всех n

То, что последовательность определяет целое -адическое число a, записывается так

Множество всех целых -адических чисел мы будем обозначать через . В отличае от целых -адических чисел обычные целые числа будут называться рациональными.

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

Два различных целых рациональных числа определяют разные целые -адические числа.

Так и есть, из их равенства как целых –адических чисел следовали бы при всех n сравнения , что возможно только при . Именно поэтому мы будем рассматривать множество целых рациональных чисел как часть множества целых рациональных чисел.

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

Пусть целое -адическое число задается последовательностью

Обозначим наименьшее неотрицательное число, сравнимое с по модулю ,через : , 0

Сравнение показывает, что

,

Так что последовательность определяет некоторое целое -адическое число, и притом в силу .

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

Мы доказали, следовательно, что каждое -адическое число определяется некоторой канонической последовательностью.

Легко видеть, что две разные канонические последовательности определяют разные целые -адические числа. Действительно, если канонические последовательности и определяют одно и то же целое -адическое число, то в силу сравнений и условий 0 получаем что при всех n

Таким образом, целые -адические числа находятся во взаимно однозначном соответствии с каноническими последовательностями. Из условия следует,что 0 и 0 0

Следовательно, всякая каноническая последовательность имеет вид

{,,}, где 0Очевидно, что и, наоборот , каждая последовательность такого вида является канонической последовательностью, определяющей некоторое целое -адическое число. Исходя из этого легко доказать, что множество канонических последовательностей, а следовательно и множество всех целых -адических чисел имеют мощность континуума.

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

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

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

Делимость целых -адических чисел определяется так же, как и в любом другом кольце: , если существует такое целое - адическое число , что

Для исследования свойств деления важно знать, каковы те целые - адические числа,для которых существуют обратные целые -адические числа. Такие числа называют делителями единицы или единицами. Мы их будем называть - адическими единицами.

Теорема: Целое - адическое число , определяемое последовательностью , тогда и только тогда является единицей, когда .

Доказательство:

Пусть является единицей, тогда существует такое целое - адическое число , что . Если определяется последовательностью то условие означает,что . В частности, , а значит, Обратно, пусть Из условия легко следует, что , так что . Следовательно, для любого n можно найти такое , что будет справедливо сравнение . Так как и , то . Это значит, что последовательность определяет некоторое целое - адическое число Сравнения показывают, что , т.е. что является единицей.

Из доказанной теоремы следует, что целое рациональное число . Будучи рассмотрено как элемент кольца , тогда и только тогда является единицей, когда . Если это условие выполнено, то содержится в . Отсюда следует, что любое целое рациональное b делится на такое a в ,т.е. что любое рациональное число вида b/a, где a и b целые и , содержится в Рациональные числа такого вида называются -целыми. Они образуют очевидным образом кольцо. Полученный нами результат можно теперь сформулировать так:

Следствие: Кольцо целых -адических чисел содержит подкольцо, изоморфное кольцу - целых рациональных чисел.

Дробь вида , , k >= 0 определяет дробное p-адическое число или просто p-адическое число. Две дроби, и , определяют одно и тоже p -адическое число, если в .

Совокупность всех p-адических чисел обозначается _p. Легко проверить, что операции сложения и умножения продолжаются с _p на _p и превращают _p в поле.

Теорема. Всякое p-адическое число единственным образом представляется в виде =, где m — целое число, а — единица кольца_p.

Теорема. Всякое отличное от нуля p-адическое число однозначно представляется в виде

M= .

Свойства: Поле p-адических чисел содержит в себе поле рациональных чисел. Нетрудно доказать, что любое целое p-адическое число некратное p обратимо в кольце _p , а кратное p однозначно записывается в виде , где x не кратно p и поэтому обратимо, а . Поэтому любой ненулевой элемент поля _p может быть записан в виде , где x не кратно p, а m любое; если m отрицательно, то, исходя из представления целых p-адических чисел в виде последовательности цифр в p-ичной системе счисления, мы можем записать такое p-адическое число в виде последовательности , то есть, формально представить в виде p-ичной дроби с конечным числом цифр после запятой и, возможно, бесконечным числом ненулевых цифр до запятой. Деление таких чисел можно также производить аналогично «школьному» правилу, но начиная с младших, а не старших разрядов числа.

Объяснение р-адических чисел с помощью ввода новых математических объектов

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

Пример: ...3819248393684028831439284578

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

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

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

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

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

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

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

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

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

−...000000023 = ...999999977

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

−...000000101 = ...111111011

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

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

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

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

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

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

Доказательство.

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

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

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

x₀ · y_i + x_i · y₀ + C = 0

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

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

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

Пример выполнения арифметических операций над 5-адическими числами.

Пример выполнения деления 5-адических чисел.

Наглядности ради, p-адические числа можно уподобить ветвям и листьям огромного раскидистого дерева. Если представить, что такое дерево выросло из некоторой определенной точки на числовой прямой, то обнаруживается удивительное соответствие этих множеств. То есть ветвей и листьев на математическом дереве настолько много, что для любой точки на числовой оси можно найти соответствующую величину и на древовидной структуре – продвигаясь по дереву согласно строго определенным правилам.

В данном параграфе мы выяснили, что такое p-адические числа. Они почти не отличаются от вышеописанных квазибесконечных чисел, однако имеют следующие особенности: основание системы счисления – всегда простое число; цифры записываются в обратном порядке по сравнению с вышеописанным (т. е. бесконечный хвост уходит вправо, а не влево; однако это лишь форма записи, суть от этого не меняется).

3. Арифметика вычетов по модулю m

При сложении двух однозначных чисел может получиться либо однозначное число, например 1 + 4 = 5, 7 + 2 = 9, либо двузначное число, например 3 + 9 = 12, 5 + 8 = 13, 7 + 9 = 16, 4 + 6 = 10. Условимся, если сумма двузначная, оставлять только последнюю цифру и писать 3+9=2, 5+8=3, 7+9=6, 4+6=0.

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

При перемножении двух однозначных чисел может получиться либо однозначное число: 2*3 = 6, 1*8 = 8, 3*3 = 9, либо двузначное число: 6 * 7 = 42, 7* 8 = 56, 9 * 9 = 81. В случае, если произведение двузначно, будем брать только последнюю цифру и писать 6*7 = 2, 7*8 = 6, 3*3 = 9.

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

В частности остаются верными формулы:

а+(в+с)=(а+в)+с, а+в=в+а, а(вс)=(ав)с, а(в+с)=ав+ас, а также формулы

,

,

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

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

Нашу новую арифметику мы будем называть арифметикой вычетов по модулю 10, или 10-арифметикой, потому что в ней только 10 чисел: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Составим таблицы сложения и умножения в 10-арифметике:

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

В 7-арифметике семь чисел: 0, 1, 2, 3, 4, 5, 6. Сложение и умножение в 7-арифметике определяются следующими правилами: чтобы сложить два числа, надо найти их сумму в смысле обычной арифметики и затем взять остаток от деления этой суммы на 7; чтобы перемножить два числа, надо найти их обычное произведение и взять остаток от деления его на 7. Например, 3+5=1, 4+6=3, 3+4=0, 5*3=1, 3*6=4, 2*6=5.

Разобранные нами 10-арифметика и 7-арифметика являются частными видами арифметики вычетов по модулю m, или m-арифметики. Пусть m-любое целое положительное число. Элементами m-арифметики являются числа 0, 1, 2, …, m-1. Сложение и умножение в m-арифметике определяются следующим образом: чтобы сложить (или перемножить) два числа, надо взять остаток от деления на m их обычной суммы (соответственно произведения).

Вычитание в m-арифметике, подобно обычной арифметике, определяется как действие, обратное сложению: число х называется разностью чисел b и a (x=b-a), если a+x=b.

Например, в 7-арифметике 2-5=4, либо 5+4=2.

Самый быстрый способ для вычислениях разности двух чисел в m-арифметике следующий: надо найти разность в обычном смысле и, если она отрицательна, увеличить ее на m. Например, в 7-арифметике 1-5=-4=3.

Вычитание в m-арифметике всегда возможно и приводит к единственному ответу. Употребление для m-арифметической операции вычитания обычного знака «-» оправдано тем, что если формула из обычной алгебры верна и содержит только знаки «+», «-», «*» и любое число скобок, то такая формула остается верной и при m-арифметическом истолковании встречающихся в них знаков.

m-арифметика применяется к обычной арифметике для проверки действий сложения, вычитания и умножения. При этом пользуются тем, что верное равенство из обычной арифметики превращается в верное равенство из m-арифметики, если заменить каждое число его остатком от деления на m.

Последовательность элементов m-арифметики называется m-арифметическим рядом Фибоначчи, если для (сложение понимается в смысле m-арифметики). Как в обычной арифметике, m-арифметический ряд Фибоначчи полностью определяется своими двумя начальными членами . Например, ряд , начинающийся с чисел 4, 5, имеет вид 4,5,9,3,1,4,5,…

Особенное значение имеет ряд, начинающийся элементами 0,1. Его будем называть рядом , а его члены обозначать буквами Например, ряд запишется так: 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, …

Заметим еще, что если под каждым из чисел ряда 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … написать остаток от деления этого числа на m, то остатки образуют m-арифметический ряд Фибоначчи .

Система элементов m-арифметики, выписанных по кругу, на равных расстояниях друг от друга, называется круговым m-арифметическим рядом Фибоначчи, или сокращенно рядом (читается с дугой), если при движении по часовой стрелке каждый член ряда равен сумме двух членов, ему предшествующих. На рис. 2 даны примеры рядов .

Рис. 2

Мы будем называть ряд рядом без повторений, если он не может совместиться с собой при повороте на угол, больший 0, но меньший 360 градусов.

Из приведенных на рис. 2 рядов первый и третий являются рядами без повторений. Второй ряд является рядом с повторениями, ибо он совмещается с собой при повороте на 180 градусов. Заметим, что если в некотором круговом ряде встречается дважды одна и та же пара соседних элементов, то этот ряд является рядом с повторениями.

Любой m-арифметический ряд Фибоначчи является периодическим. Поэтому при изучении такого ряда достаточно иметь дело с первыми его членами, составляющими период. Если выписать эти числа по кругу по часовой стрелке, то получится круговой m-арифметический ряд Фибоначчи без повторений.

Последовательность элементов из m-арифметики называется геометрической прогрессией, если каждый ее член, начиная с , получается из предыдущего члена умножением на одно и то же постоянное число q - знаменатель прогрессии. Например, в 7-арифметике при , q=3 имеем геометрическую прогрессию 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, …;

в 12-арифметике при , q=2 1, 2, 4, 8, 4, 8, 4, …

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

m-арифметика полезна при изучении треугольника Паскаля.

Треугольником Паскаля называется следующая бесконечная таблица чисел:

Каждое число в этой таблице равно сумме двух чисел, стоящих над ним слева и справа. Треугольник Паскаля симметричен относительно своей биссектрисы. Строки треугольника нумеруются сверху с нулевой строки.

Будем изучать свойства делимости членов треугольника Паскаля. С этой целью рассмотрим m-арифметический треугольник паскаля, который определяется совершенно так же, с той только разницей, что его членами будут уже не обыкновенные числа, а элементы m-арифметики.

Составим 3-арифметический треугольник Паскаля

Рис. 3

Мы видим, что он (по крайней мере в той его части, которая изображена на схеме) составлен из треугольников трех типов, обращенных вершинами вверх:

Рис. 4

Такие треугольники называются элементарными, и кроме того, из треугольников, обращенных вершинами вниз, которые сплошь заполнены нулями. Сумма треугольников есть треугольник, члены которого получаются суммированием соответствующих членов слагаемых треугольников. Тогда, как видно из схемы, каждый элементарный треугольник есть сумма двух элементарных треугольников, над ним стоящих. Другими словами, 3-арифметический треугольник Паскаля составлен из элементарных треугольников так же, как из чисел. Этот факт, устанавливающий известную периодичность в строении треугольника Паскаля, носит общий характер, то есть выполняется в любой m-арифметике.

Треугольники, с одинаковым числом строк можно складывать между собой и умножать на число.

Рис. 5

Таким образом, в данном параграфе мы рассмотрели применение m-арифметики.

Список использованной литературы

1. Богомолов, Н.В. Сборник задач по математике [Текст] / Н.В. Богомолов. – М.: Дрофа, 2009. – 206 с.

2. Бухштаб, А.А. Теория чисел [Текст] / А.А. Бухштаб. – М.: Просвещение, 1966. – 384 с.

3. Выгодский, М.Я. Справочник по элементарной математике [Текст] / М.Я. Выгодский. – М.: Дрофа, 2006. – 509 с.

4. Журбенко, Л.Н. Математика в примерах и задачах [Текст] / Л.Н. Журбенко. – М.: Инфра-М, 2009. – 373 с.

5. Иванов, О.А. Элементарная математика для школьников, студентов и преподавателей [Текст] / О.А. Иванов. – М.: МЦНМО, 2009. – 384 с.

6. Карп, А.П. Задания по алгебре и началам анализа для организации итогового повторения и проведения аттестации в 11 классе [Текст] / А.П. Карп. – М.: Просвещение, 2005. – 79 с.

7. Куланин, Е.Д. 3000 конкурсных задач по математике [Текст] / Е.Д. Куланин. – М.: Айрис-пресс, 2007. – 624 с.

8. Лейбсон, К.Л. Сборник практических заданий по математике [Текст] / К.Л. Лейбсон. – М.: Дрофа, 2010. – 182 с.

9. Манова, А.Н. Математика. Экспресс-репетитор для подготовки к ЕГЭ: уч. пособие [Текст] / А.Н. Манова. – Ростов-на-Дону: Феникс, 2012. – 541 с.

10. Михелович, Ш.Х. Теория чисел [Текст] / Ш.Х. Михелович. – М.: Высшая школа, 1967. – 336 с.

11. Сергеев, И.Н. ЕГЭ: 1000 задач с ответами и решениями по математике. Все задания группы С [Текст] / И.Н. Сергеев. – М.: Экзамен, 2012. – 301 с.

12. Соболев, А.Б. Элементарная математика [Текст] / А.Б. Соболев. – Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. – 81 с.

26