НОК (наименьшее общее кратное)

Если a₁\b, a₂\b, … , a_n\b, то b называется общим кратным чисел a₁,…,a_n. Наименьшее положительное общее кратное чисел a₁,…,a_n называется их наименьшим общим кратным (НОК).

Пусть НОД(a,b)=d, тогда можно записать a=d∙a₁, b=d∙b₁, где (a₁,b₁)=1.

Пусть a\M, b\M M=ak для некоторого целого k, и тогда число – целое. Но, поскольку (a₁,b₁)=1, то b₁\k , и тогда k=b₁t для некоторого , и

. *

Очевидно, , М – общее кратное a и b, и (*) дает формулу всех общих кратных.

При t=1 имеем M=НОК(a,b).

Формулой M = НОК(a,b)∙t можно представить все общие кратные чисел a и b. ( ).

Простые числа

Числа a₁,…,a_n называются взаимно простыми, если НОД(a₁,…,a_n)=1, попарно простыми, если , НОД(a_i,a_j)=1.

Если числа попарно a₁,…,a_n простые, то они взаимно простые. Обратное неверно.

Число p называется простым, если оно имеет лишь два делителя – “1” и р.

Число “1” делится только на себя, и не является ни простым, ни составным, а занимает особое место в теории чисел.

Число а>1 имеющее более двух делителей, называется составным.

Утверждение 1

Наименьший не равный единице делитель числа a: , >1, является простым числом.

Доказательство:
Пусть q: q>1, q\a – наименьший делитель а. Если бы q было составным, то нашлось бы число q₁>1: q₁\q, и тогда для некоторого целого k выполнялось бы q=kq₁ a=qt=q₁kt q₁\a, q₁<q (то есть нашелся делитель числа a, который меньше q) q – не наименьший делитель числа a. Пришли к противоречию с условием теоремы. Предположение неверное, следовательно верно обратное. q – простое число.

□

Утверждение 2

p – наименьший делитель составного числа а, p≠1 .

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

Представим a в виде a=pa₁. Поскольку p – наименьший делитель числа a, то a₁≥p a≥p² в силу монотонности квадратичной функции на положительной полуоси, p≤ .

□