C, PHP, VB, .NET

Нека N и P са естествени числа такива, че N > P > 2. Искаме да проверим дали N се дели без остатък на P. Ще покажа един алгоритъм за намиране на почти универсален „признак за делимост“. Казвам „почти“, защото не работи за всички числа P.

В началото нека кажем няколко основни признаци за делимост, които се учат още в ранните класове в училище:

Признак за деление на 2: Ако числото е четно, то се дели на 2.

Признак за деление на 3: Ако сборът от цифрите на числото се дели на 3, то числото също се дели на три.

Признак за деление на 5: Ако числото завършва на цифрата 5 или на 0, то числото се дели на 5.

Сега ще изведем едно по-общо правило. Както знаем всяко число N може да се представи чрез две други цели положителни числа a и b по следния начин:

N = 10.a + b (*)

Твърдение 1. Нека x е най-малкото естествено число такова, че x.P = 10.y + 1, тоест произведението x.P завършва на цифрата 1. Числото N от (*) се дели без остатък на P тогава и само тогава когато (a – y.b) се дели без остатък на P.

Доказателство: Умножаваме двете страни на равенство (*) по числото (-y), с което равенството не се променя:

-y.N = -10.y.a – y.b

Прибавяме от двете страни на равенството числото (10.y + 1).a, с което равенството не се променя:

(10.y + 1).a – y.N = (10.y + 1).a – 10.y.a – y.b

=> (10.y + 1).a – y.N = 10.y.a + a – 10.y.a – y.b

Заместваме (10.y + 1) с x.P:

x.a.P – y.N = a – y.b

Необходимост: Нека N се дели на P, т.е. съществува число r такова, че N = r.P

=> x.a.P – y.r.P = a – y.b

=> P(x.a – y.r) = a – y.b

=> a – y.b се дели на P

Достатъчност: Нека a – y.b се дели на P, т.е. съществува число q такова, че a – y.b = q.P

=> y.N = x.a.P – q.P

=> y.N = P(x.a – q)

=> N се дели на P.

Твърдение 2. Нека x е най-малкото естествено число такова, че x.P = 10.y + 9, тоест x.P завършва на цифрата 9. Числото N от (*) се дели на P тогава и само тогава когато числото (a + (y+1).b) се дели на P.

Доказателство: Оставям го на читателите.

Алгоритъм за намиране на признак за делимост: Нека имаме число N и искаме да проверим дали то се дели на P. Започваме да умножаваме числото P с естествените числа 1, 2, 3, 4 … и т.н. докато намерим най-малкото число x такова, че числото x.P = 10.y + 1 или x.P = 10.y + 9.

1. Ако x.P завършва на цифрата 1, то проверяваме дали a – y.b се дели на P. Ако да, то и числото N се дели на P.

Например: Нека P = 37. Търсим числото x:

• 1.37 = 37 – не завършва нито на 1, нито на 9;
• 2.37 = 74 – не;
• 3.37 = 111 – да, завършва на 1 => x = 3.

=> x.P = 3.37 = 111 = 11.10 + 1

=> y = 11.

Искаме да проверим дали числото N = 11877 се дели на 37. Преобразуваме N = 10.1187 + 7

=> a = 1187 и b = 7

=> Проверяваме дали a – y.b = 1187 – 7.11 = 1110 се дели на 37. За това число можем да приложим същите твърдения:

=> Проверяваме дали 111 – 0.37 = 111 се дели на 37. За това число можем да приложим същите твърдения:

=> Проверяваме дали 11 – 1.11 = 0 се дели на 37 – да, дели се на 37 без остатък. Следователно и числото N = 11877 също се дели на 37!

2. Ако числото x.P завършва на цифрата 9, то проверяваме дали a + (y+1).b се дели на P. Ако да, то и числото N се дели на P.

Например: Нека P = 29. Търсим числото x:

• 1.29 = 29 – да, завършва на 9 => x = 1.

=> x.P = 1.29 = 29 = 10.2 + 9

=> y = 2

Искаме да проверим дали числото N = 19082 се дели на 29. Преобразуваме N = 10.19082 + 2

=> a = 19082 и b = 2

=> Проверяваме дали a + (y+1).b = 1908 + 3.2 = 1914 се дели на 29. За това число можем да приложим същите твърдения:

=> Проверяваме дали 191 + 3.4 = 203 се дели на 29. За това число можем да приложим същите твърдения:

=> Проверяваме дали 20 + 3.3 = 29 се дели на 29. Да, 29 се дели на 29 => и числото N = 19082 също се дели на 29.

Твърдение 3. Алгоритъмът НЕ е универсален

Доказателство: Този алгоритъм не работи за четните числа, защото ако P e четно, то не съществува число x такова, че x.P  да завършва на 1 или на 9. Също така друг пример е числото 5 – не можем да намерим число x такова, че x.5 да завършва на 1 или на 9.

От казаното дотук оставаме с впечатление, че предложения алгоритъм не работи за повечето числа. Истината обаче е, че влиза в приложение почти винаги. Например ако търсим признак за деление на P, което е четно, то може да представим P = 2.Q. От там заключваме, че признакът на деление на P е числото N да се дели едновременно и на 2 и на Q. Така рекурсивно ние пак рано или късно достигаме до използване на алгоритъма представен по-горе чрез признакът на деление на Q.

Например ако търсим признак за деление на P = 116. Представяме P = 2.2.29. От тук казваме, че N трябва да се дели едновременно на 4 и на 29, като за второто ще използваме показания по-горе алгоритъм.

Друг пример – търсим признак за деление на P = 312. Представяме P = 2.2.2.39. От тук казваме, че N трябва да се дели едновременно на 8 и на 39, като за второто използваме показания по-горе алгоритъм.

Виждаме, че при четните числа се налага често да доказваме признаци за делимост на числа степени на двойката. За щастие те се извеждат изключително лесно:

Признак за делимост на 2 = 2¹: Последната цифра на числото трябва да се дели на 2.

Признак за делимост на 4 = 2²: Последните 2 цифри на числото трябва да се делят на 4.

Признак за делимост на 8 = 2³: Последните 3 цифри на числото трябва да се делят на 8.

…

Признак за делимост на P = 2ⁿ: Последните n цифри на числото трябва да се делят на P.

Чрез показания алгоритъм можете да изведете признаците на делимост на почти всяко просто число (за сега се сещам само за изключения невъзможните 2 и 5, но може би има и още), а от там да го използвате за признак на делимост и на всяко съставно число.

Задача: Изведете признаците за делимост на числата от 1 до 50.