Отношение делимости и его свойства

Делимость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Если для некоторого целого числа [math]a[/math] и целого числа [math]b[/math] существует такое целое число [math]q[/math], что [math]bq = a[/math], то говорят, что число [math]a[/math] делится нацело на [math]b[/math] или что [math]b[/math] делит [math]a[/math].

При этом число [math]b[/math] называется делителем числа [math]a[/math], делимое [math]a[/math] будет кратным числа [math]b[/math], а число [math]q[/math] называется частным от деления [math]a[/math] на [math]b[/math].

Свойства: Замечание: — целые числа. Любое целое число является делителем нуля, и частное равно нулю : Любое целое число делится на единицу: Для любого целого числа найдётся такое целое число для которого Если и то Отсюда же следует, что если и то Если то

Свойство делимости является отношением нестрогого порядка и, в частности, оно:

рефлексивно — любое целое число делится на себя же:
транзитивно — если и то
антисимметрично — если и то либо либо

Деление числа на число с остатком

Алгоритм Евклида

НОД и его свойства

Взаимно-простые числа

НОК и его свойства

Простые и составные числа и их свойства

Теорема Евклида

Теорема (Евклида):

Я тян

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

Пруфов не будет

Теорема об интервалах и об оценке простых делителей

Свойства сравнений

Классы вычетов. Теоремы о линейных формах

Полная и приведенная системы вычетов

Функция Эйлера и ее свойства

Тождество Гаусса

Теоремы Эйлера и Ферма

Теорема (Эйлера):

Теорема (Ферма):

Равносильность сравнений. Сравнения высших степеней. Теорема Лагранжа

Теорема (Лагранжа):

Системы линейных уравнений. Китайская теорема об остатках

Теорема (Китайская теорема об остатках):

Жил был китаец. Он умер и ничего не оставил

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

Так сказал адвокат.

Линейные сравнения и линейные диофантовы уравнения

Теоремы Вильсона и Лейбница

Теорема (Вильсона):

Теорема (Лейбница):

Следствия из теоремы Вильсона. Обобщенная теорема Вильсона

Порядок числа и его свойства

Первообразные корни по простому модулю

Индекс и его свойства

Конечные цепные дроби. Закон образования подходящих дробей

Свойства подходящих дробей

Представление иррационального числа цепной дробью. Рациональные приближения иррационального числа. Теорема Лагранжа