Универсален алгоритъм за намиране на признаци за делимост на прости числа(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.
В следващ блог ще разгледам някои примери.

Хамилтон

Хамилтон, Уилям Роуън, род. 04.08.1805 г. в Дъблин, почива 02.09.1865 в Дънсик.
От 1824 г. Хамилтон следва в Дъблин и още през 1827 г. преди да е завършил следването си, става професор по астрономия и кралски астроном на Ирландия. Има важни работи в областта на алгебрата и е откривател на кватернионите. Изключително важни са приносите му към геометричната оптика и класическата механика, между които са и каноничните уравнения и принципът на Хамилтън.
"Математически енциклопедичен речник" В.Гелерт и др. "Наука и изкуство"

Вен

Вен, Джон роден на 04.08.1834 г. в Хъл, почива на 04.04.1923 г. в Кеймбридж. Става свещеник през 1859 г. и работи като професор по логика и натурална философия в Кеймбридж. Развива индуктивна и методологична логика и се опитва да я свърже с дедуктивната и формализирана логика на Хамилтон.
"Математически енциклопедичен речник" В.Гелерт и др. "Наука и изкуство"

Принцеса или тъгър - II

Първи ден - второ изпитание
(Продължение на Принцеса или тигър - I)

И така, първият затворник си спасил живота и отвел със себе си прекрасна принцеса. Надписите на стаите били сменени - съответно и обитателите на стаите.
Ето какви надписите закачени на вратите на стаите:

I - ва стая

В поне една от двете стаи има принцеса.

II - ра стая

Тигърът е в другата стая.

- Истинни ли са твърденията на надписите? - попитал вторият затворник.
- Може и двете да са истина, а може и двете да са лъжа - отговорил царят.
Коя от стаите трябва да избере затворникът?

Принцеса или тъгър - I

В едно царство управлявал цар. Веднъж той казал на своя министър:
- Трябва да измисля нещо за мойте затворници осъдени на смърт. Да им дам възможност да се спасят, но възможност която ще покаже, че заслужават да живеят.
- Чудесно Ваше Величество! - възликнал министърът.
- Ако един затворник не е глупак и умее да расъждава логично той ще може да спаси живота си и ще получи прекрасна невеста за жена.
- Блестяща идея Ваше Величество! - какво друго могъл да каже министърът.
За първият ден били предвидени три изпитания. При това царят казал на на затворника, че в хода на всички три изпитания във всяка стая ще се намира или принцеса, или тигър, но е напълно възможно във всички стаи да има само тигри или само принцеси. Затворника трябва да избере една от двете стаи, ако в стаята има тъгър затворникът става храна за тъгъра, иначе ако има принцеса ще се ожени за нея.
- А ако във всички стаи има тигри? - попитал затворникът.
- Смятай, че не ти е провървяло.
- А ако във всички стаи има принцеси? - отново попитал затворникът.
- Е, тогава си късметлия.
- Добре, но ако в една стая има принцеса в друга тигър, какво да правя тогава ?!?!?
- Е, тогава нещата зависят от теб.
И царят насочил погледа на затворника към надписите на вратите на стаите:

Първи ден - първо изпитание

I - стая
В тази стая се намира принцеса, а в другата стая има тигър.
II - стая
В една от тези стаи има принцеса; освен това в една от тези стаи има тигър.

- А истина ли е това което е написано на надписите? - попитал затворникът.
- На едната е истина - отговорил царят - на другата не е.

Бихте ли могли да разберете къде е принцесата? Разбира се, ако не предпочитате тигър.
(По Реймънд Смалиан)