Универсален алгоритъм за намиране на признаци за делимост на прости числа(prime numbers).

Тук ще продължа статията Признаци за делимост на прости числа. Ще се опитам да формулирам общ признак за делимост на дадено число на дадено друго просто число.

Нека имаме цяло число z=a₁₁a₁₂ ... a_1(n-1)a_1n и просто число p(prime number). Където a₁₁, a₁₂ , ... , a_1(n-1), a_1n са цифрите на числото z в десетична бройна система.
Образуваме:
z₁₁=a₁₁a₁₂ ... a_1(n-1)
и
z₁₂= a_1n
Тогава твърдя, че ако p|z съществува най-малко цяло число e, такова че:
p | z₁₁ + z_12*e.
Нека сега да искаме да проверим дали p|z (при горните означения и намереното e). Образуваме:
(1) z₁ = z₁₁ + z_12*e.
За z₁ образуваме:
z₂₁=a₂₁a₂₂ ... a_2(n-2)
и
z₂₂= a_2(n-1)
където a₂₁a₂₂ ... a_2(n-2)a_2(n-1) са цифрите на числото z₁ в десетичена бройна система.
Нека z₂ = z₂₁ + z_22*e.
За z₂ изпълняваме същата операция (1) както за z₁ . Продължаваме, догато не достигнем в (1) число, за което в операцията (1) се получава едно и съща стойност или най-малкото от редицата z, z₁, z₂, ... , z_к. Така получено число z_к е вече достатъчно малко и лесно може да се провери дели ли се на p.
Така: ако искаме да проверим дали дадено число z се дели на просто число p, то за така намереното e прилагаме горният алгоритъм.Ако достигнем до число, което се дели на p, то и z се дели на p, а ако достигнем до число, което не се дели на p, то и z не се дели на p.
В следващ блог ще разгледам някои примери.