Критерий простоты натурального числа

[Побережный Александр]

Критерий простоты
Пусть задано натуральное число $A$.
Если для любого натурального числа $k$, где $1<k\leqslant\sqrt{A}$ выполняется НОД$(k;A-k)=1$, то число $A$ есть простое число.
НОД - наибольший общий делитель.

Следствие.
Если НОД$(k;A-k)=a\not =1$, тогда число $a$ содержит множитель $p$, на который делится и число $A$.

[mihaild]

Ну да, если $A$ делится на $k$, то $\gcd(k, A - k) = k$, а если $A$ составное, то оно делится на какое-то число из $(1, \sqrt{a}]$.