Принцип отражения в множестве натуральных чисел план

Умножение
Воспользуемся определением натуральных чисел NN как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств порождённых биекциями, с помощью скобок: [C],[A],[B].[C],[A],[B]. Тогда арифметическая операция умножение определяется следующим образом: где: прямое произведение множеств — множество C,C, элементами которого являются упорядоченные пары (a, b)(a, b) для всевозможных a∈A, b∈Ba∈A, b∈B. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.
Вычитание
Воспользуемся определением натуральных чисел NN как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств C,A,BC,A,B порождённых биекциями, с помощью скобок: [C], [A], [B].[C], [A], [B]. Тогда арифметическая операция вычитание определяется следующим образом: где A∖B={C∈A∣C∉B∣B⊂A}— A∖B={C∈A∣C∉B∣B⊂A}— разность множеств. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.

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

Определение:

Если натуральное число nn не делится на натуральное число mm, т.е. не существует такого натурального числа kk , что n=m⋅kn=m⋅k, то деление называется делением с остатком (англ. modulo operation).

Формула деления с остатком: n=m⋅k+r,n=m⋅k+r, где nn — делимое, mm — делитель, kk — частное, rr — остаток, причем 0⩽rЛюбое число можно представить в виде: n=2⋅k+rn=2⋅k+r, где остаток r=0r=0 или r=1r=1
Любое число можно представить в виде: n=4⋅k+rn=4⋅k+r, где остаток r =0r =0 или r=1r=1 или r=2r=2 или r=3r=3
Любое число можно представить в виде: n=m⋅k+rn=m⋅k+r, где остаток rr принимает значения от 00 до (m−1)(m−1)
Основная теорема арифметики
Лемма Евклида

Лемма:

Если простое число pp делит без остатка произведение двух целых чисел x⋅yx⋅y, то pp делит xx или yy.

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

▹▹

Пусть x⋅yx⋅y делится на pp, но xx не делится на pp. Тогда xx и pp — взаимно простые, следовательно, найдутся такие целые числа uu и vv, что x⋅u+p⋅v=1x⋅u+p⋅v=1 (соотношение Безу). Умножая обе части на yy, получаем (x⋅y)⋅u+p⋅v⋅y=y.(x⋅y)⋅u+p⋅v⋅y=y. Оба слагаемых левой части делятся на pp, значит, и правая часть делится на pp.