Исследовательская работа по математике «Сравнения в кольце целых чисел и их применения» (стр. 3 )

Определение 2. Наибольшим общим делителем класса называется наибольший общий делитель чисел и . Если , то класс называется взаимно простым с модулем .

Определение 3. Система вычетов, взятых по одному из каждого класса, взаимно простого с модулем называется приведенной системой вычетов (обозначается ПрСВ).

Классы вычетов по модулю.

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

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

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

Определение. Каждое натуральное число единственным образом представимо в виде ,где — простые числа, и — некоторые натуральные числа.

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

Примеры.

Теорема 1. Если - каноническое разложение числа на простые множители, то .

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

Пример.

Теорема Эйлера. Если - натуральное число, и , то  .

Теорема Ферма. Если число - простое, и , то  .

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

Решение. Так как девятая степень числа оканчивается цифрой 7, то остаток от деления числа на 10 должен быть равен 7, что равносильно справедливости сравнения  .

Так как , то . Воспользовавшись теоремой Эйлера, получим: , где .

Возведем обе части последнего сравнения в квадрат, получим  . Тогда сравнение   можно записать в виде: . А так как , то исходное сравнение примет вид: .