кольцо вычетов системы вычетов
Кольцо вычетов
Сравнение по модулю натурального числа — отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются) после достижения определенного значения.
В дискретной математике, для сравнений по модулю используется также термин модульная (или модулярная) арифметика.
Содержание
Определения
Утверждение « a и b сравнимы по модулю n » записывается в виде:
Свойства
Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если
Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: 
, однако, сократив на 2, мы получаем ошибочное сравнение: 
. Правила сокращения для сравнений следующие.
Нельзя также выполнять операции со сравнениями, если их модули не совпадают.
Классы вычетов
Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел 
, то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается 
или 
.
Операции сложения и умножения на индуцируют соответствующие операции на множестве :
[a]n + [b]n = [a + b]n 
Относительно этих операций множество является конечным кольцом, а если n простое — конечным полем.
Решение сравнений
Сравнения первой степени
В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:
Решение такого сравнения начинается с вычисления НОД(a, m)=d. При этом возможны 2 случая:
Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:
Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: 
, эквивалентное двум решениям по модулю 22: 
.
Сравнения второй степени
Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.
История
В значительной степени теория делимости и вычетов была создана Эйлером. Сравнения по модулю впервые использовались Гауссом в его книге «Арифметические исследования», 1801 год. Он же предложил утвердившуюся в математике символику для сравнений.
Ссылки
Полезное
Смотреть что такое «Кольцо вычетов» в других словарях:
Кольцо (алгебра) — Кольцо это множество, на котором заданы две операции, «сложение» и «умножение», со свойствами, напоминающими сложение и умножение целых чисел. Содержание 1 Определения 2 Связанные определения 3 Простейшие свойства … Википедия
Кольцо (множество) — Кольцо это множество, на котором заданы две операции, «сложение» и «умножение», со свойствами, напоминающими сложение и умножение целых чисел. Содержание 1 Определения 2 Связанные определения 3 Простейшие свойства … Википедия
Кольцо (математика) — У этого термина существуют и другие значения, см. Кольцо. В абстрактной алгебре кольцо это один из наиболее часто встречающихся видов алгебраической структуры. Простейшими примерами колец являются алгебры чисел (целых, вещественных,… … Википедия
Кольцо алгебраическое — Кольцо алгебраическое, одно из основных понятий современной алгебры. Простейшими примерами К. могут служить указанные ниже системы (множества) чисел, рассматриваемые вместе с операциями сложения и умножения: 1) множество всех целых положительных … Большая советская энциклопедия
Кольцо — алгебраическое, одно из основных понятий современной алгебры. Простейшими примерами К. могут служить указанные ниже системы (множества) чисел, рассматриваемые вместе с операциями сложения и умножения: 1) множество всех целых положительных … Большая советская энциклопедия
Кольцо когомологий — Гомология одно из основных понятий алгебраической топологии. Замкнутая линия гомологична нулю, если она ограничивает кусок поверхности, который отделяется от неё, если мы произведём разрез по этой линии. Например, на сфере любая замкнутая линия… … Википедия
Мультипликативная группа кольца вычетов — Приведённая система вычетов по модулю m множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) функция Эйлера. В качестве приведённой системы вычетов… … Википедия
АНАЛИТИЧЕСКОЕ КОЛЬЦО — кольцо ростков аналитич. функций в точке аналитического пространства. Более точно: пусть kесть поле с нетривиальным абсолютным значением (обычно предполагаемое полным) и есть fc алгебра степенных рядов от с коэффициентами в k, сходящихся в нек… … Математическая энциклопедия
ЛОКАЛЬНОЕ КОЛЬЦО — коммутативное кольцо с единицей, имеющее единственный максимальный идеал. Если А Л. к. с максимальным идеалом то факторкольцо является полем и наз. полем вычетов Л. к. А. Примеры Л. к. Любое поле или кольцо нормирования является локальным.… … Математическая энциклопедия
ДИСКРЕТНОГО НОРМИРОВАНИЯ КОЛЬЦО — дискретно нормированное кольцо, кольцо с дискретным нормированием, т. е. область целостности с единицей, в к рой существует такой элемент я, что любой ненулевой идеал порождается нек рой степенью элемента я; такой элемент наз. униформизирующим и… … Математическая энциклопедия
Кольцо вычетов
Целые числа a,b сравнимы по модулю n, если при делении на число n эти числа дают один остаток (a mod n = b mod n).
При делении на n возможные значения остатка 0,1,…,n-1.
Обозначим [k] – класс сравнимых между собой чисел, дающих при делении на n остаток k. Например, для n=4 образуется четыре класса:
Таким образом, при делении на n образуется n классов [0],[1],…,[n-1]. Эти классы называются классами вычетов по модулю n. Множество Zn=<[0],[1],…, [n-1]> называется полной системой вычетов. В дальнейшем квадратные скобки будем опускать Zn=<0,1,…,n-1>.
Число из класса [a] имеет вид in+a. Выясним, в какой класс попадет сумма чисел из классов [a],[b]:
Это число при делении на n дает остаток ((i+j)n+(a+b)) mod n = (a+b) mod n. Таким образом, сумма любых двух чисел из классов [a],[b] принадлежит классу [(a+b) mod n]. В соответствии с этим на множестве Zn введем операцию сложения:
В этом соотношении слева используется алгебраическая операция над элементами a,bÎZn. Справа – арифметические операции над числами a,b,n.
Свойства введенной операции сложения:
· операция коммутативна и ассоциативна, поскольку коммутативна и ассоциативна арифметическая операция сложения в правой части соотношения a+b=(a+b) mod n.
· элемент, противоположный элементу a, определяется следующим образом —a=n—a, т.к. a+(—a)=(—a)+a=(a+n—a) mod n =0.
Таким образом, алгебра A= образует абелевую группу относительно операции сложения.
Теперь выясним, в какой класс попадет произведение чисел из классов [a],[b]:
Это число при делении на n дает остаток (ab) mod n.
Поэтому операция умножения на множестве Zn определяется как:
В этом соотношении слева – алгебраическая операция над элементами a,bÎZn. Справа – арифметические операции над числами a,b,n.
Свойства введенной операции умножения:
· операция умножения коммутативна и ассоциативна, поскольку коммутативна и ассоциативна арифметическая операция умножения в правой части соотношения a*b=(ab) mod n.
Такую алгебру называют кольцом вычетов.
Кроме того, в кольце вычетов выполняется условие коммутативности умножения, следовательно, данная алгебра является коммутативным кольцом.
Если n – составное, то кольцо вычетов содержит делители нуля. Действительно, если n=kl, тогда по определению умножения k*l=(kl) mod n =0.
Результаты операций сложения умножения и вычитания в A= представлены в табл.1.2-1.4 соответственно. Делителями нуля является пара элементов a=2,b=2.
Материал для подготовки к разделу «Арифметика вычетов»
1. Арифметика вычетов
В отличие от (1) операция означает остаток от деления (например, ). Эта операция называется приведением по модулю.
Далее приведены свойства функции сравнения:
Сравнения по одинаковому модулю можно почленно складывать.
Обе части сравнения можно возвести в одну и ту же степень.
Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.
Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.
Если сравнение имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.
К обеим частям сравнения можно прибавить одно и тоже число; обе части сравнения можно умножить на одно и тоже число.
Свойство операции приведения по модулю:
Проверим свойство операции приведения:
Найдем при помощи свойства операции приведения по модулю:
Такой прием называется цепочкой разложения, в основе которой лежит двоичное представление числа.
Свойства классов вычетов:
Любые чисел попарно не сравнимые по модулю образуют полную систему вычетов.
Полная система вычетов – это совокупность вычетов, взятых по одному из каждого класса эквивалентности.
Рис. 1. Иллюстрация к образованию классов вычетов по модулю 8
На рис. 1 изображен процесс «наматывания» цепочки целых чисел на колечко с делениями, при этом на одно деление автоматически попадают сравнимые между собой числа.
Свойства функции Эйлера:
Алгоритм Евклида (применяется при небольших для нахождения : ).
Выполним следующие деления с остатком:
Найдем линейное разложение НОД’а: :
Отрицательным моментом этого метода является то, что необходимо возводить в степень.
Свойства данного числа :
По любому простому модулю существует первообразный корень.
Значит, первообразными корнями по модулю являются 3 и 5.
Таким образом, в данном параграфе мы раскрыли основные понятия арифметики вычетов, такие как сравнения в кольце целых чисел, основные теоремы и свойства сравнений.
Итак, рассмотрим сравнение: по степеням простого числа 7. При n =1 сравнение имеет два решения:
Таким образом, получаем решение
Аналогично при n =3 получаем и из сравнения
Этот процесс мы можем продолжать бесконечно.
Мы получим последовательность
Она обладает свойствами:
Итак, процесс построения последовательности
Чем-то напоминает процесс извлечения квадратного корня из 2.
При возрастании n становится сколь угодно 7-близкими к 2.
Можно предположить, что наша последовательность так же определяет число a некоторой новой природы, причем такое, что =2.
Сравнение показывает, что
То же самое, что и последовательность Последовательность, все члены которой удовлетворяют условиям и 0, будем называть канонической.
Следовательно, всякая каноническая последовательность имеет вид
Теорема. Всякое отличное от нуля p-адическое число однозначно представляется в виде
Объяснение р-адических чисел с помощью ввода новых математических объектов
«Квазибесконечным числом» (КБЧ) называется бесконечная последовательность цифр (из какой-либо системы счисления, например десятичной), идущая справа налево.
Эти числа названы «квазибесконечными», потому что они кажутся бесконечными, но на самом деле не являются таковыми.
Рассмотрим те КБЧ, в которых влево от некоторой позиции идут одни нули, например:
Нетрудно заметить, что такие числа при сложении и умножении ведут себя как обычные неотрицательные целые числа.
1) Каждую цифру x i заменить на (N−1)−x i (где N — основание системы счисления)
Например, в десятичной системе:
В двоичной системе:
Таким образом, те КБЧ, в которых влево от некоторой позиции идут одни только наибольшие цифры данной системы счисления, можно отождествить с обычными отрицательными целыми числами.
Сумма двух КБЧ вычисляется справа налево по обычному методу сложения столбиком (вычисляется сумма двух цифр очередного разряда, прибавляется единица при наличии переноса из предыдущего разряда, затем определяется цифра суммы данного разряда и наличие переноса в следующий разряд). [В нижеприведённых таблицах наличие переноса обозначается чертой над соответствующей цифрой.] Например:
Аналогично вычисляется разность двух КБЧ (только вместо переноса здесь заимствование из следующего разряда). Умножение также вычисляется по обычном методу умножения столбиком, как сумма бесконечного ряда слагаемых. Деление осуществляется подбором цифр справа налево, используя тот факт, что для вычисления n последних (правых) цифр произведения достаточно перемножить числа, образованные n последними цифрами сомножителей. (Деление выполняется проще, если основание системы счисления – простое число, иначе возникают неоднозначности в подборе цифр)
Естественно предположить, что всякое периодическое КБЧ (т. е. такое, в котором слева от некоторого разряда идёт бесконечно повторяющаяся последовательность цифр) представляет некоторую дробь (т. е. при умножении периодического КБЧ на некоторое конечное число можно получить конечное число).
Теорема. Если основание системы счисления N – простое число, то для любого числа x, не кончающегося на 0, существует обратное число x −1 (т. е. такое, что x · x −1 =1).
Далее, исходя из алгоритма умножения столбиком, для очередной цифры x i мы подберём цифру y i по уравнению
(вычисления осуществляются по модулю N; C –«довесок», образующийся от перемножения предыдущих цифр).
Поскольку x 0 ≠ 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.
Например, в 7-арифметике 2-5=4, либо 5+4=2.
Мы будем называть ряд рядом без повторений, если он не может совместиться с собой при повороте на угол, больший 0, но меньший 360 градусов.
Из приведенных на рис. 2 рядов первый и третий являются рядами без повторений. Второй ряд является рядом с повторениями, ибо он совмещается с собой при повороте на 180 градусов. Заметим, что если в некотором круговом ряде встречается дважды одна и та же пара соседних элементов, то этот ряд является рядом с повторениями.
Треугольником Паскаля называется следующая бесконечная таблица чисел:
Каждое число в этой таблице равно сумме двух чисел, стоящих над ним слева и справа. Треугольник Паскаля симметричен относительно своей биссектрисы. Строки треугольника нумеруются сверху с нулевой строки.
Составим 3-арифметический треугольник Паскаля
Мы видим, что он (по крайней мере в той его части, которая изображена на схеме) составлен из треугольников трех типов, обращенных вершинами вверх:
Треугольники, с одинаковым числом строк можно складывать между собой и умножать на число.
Список использованной литературы
Богомолов, Н.В. Сборник задач по математике [Текст] / Н.В. Богомолов. – М.: Дрофа, 2009. – 206 с.
Бухштаб, А.А. Теория чисел [Текст] / А.А. Бухштаб. – М.: Просвещение, 1966. – 384 с.
Выгодский, М.Я. Справочник по элементарной математике [Текст] / М.Я. Выгодский. – М.: Дрофа, 2006. – 509 с.
Журбенко, Л.Н. Математика в примерах и задачах [Текст] / Л.Н. Журбенко. – М.: Инфра-М, 2009. – 373 с.
Иванов, О.А. Элементарная математика для школьников, студентов и преподавателей [Текст] / О.А. Иванов. – М.: МЦНМО, 2009. – 384 с.
Карп, А.П. Задания по алгебре и началам анализа для организации итогового повторения и проведения аттестации в 11 классе [Текст] / А.П. Карп. – М.: Просвещение, 2005. – 79 с.
Куланин, Е.Д. 3000 конкурсных задач по математике [Текст] / Е.Д. Куланин. – М.: Айрис-пресс, 2007. – 624 с.
Лейбсон, К.Л. Сборник практических заданий по математике [Текст] / К.Л. Лейбсон. – М.: Дрофа, 2010. – 182 с.
Манова, А.Н. Математика. Экспресс-репетитор для подготовки к ЕГЭ: уч. пособие [Текст] / А.Н. Манова. – Ростов-на-Дону: Феникс, 2012. – 541 с.
Михелович, Ш.Х. Теория чисел [Текст] / Ш.Х. Михелович. – М.: Высшая школа, 1967. – 336 с.
Сергеев, И.Н. ЕГЭ: 1000 задач с ответами и решениями по математике. Все задания группы С [Текст] / И.Н. Сергеев. – М.: Экзамен, 2012. – 301 с.
Соболев, А.Б. Элементарная математика [Текст] / А.Б. Соболев. – Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. – 81 с.