Теория на числата - делимост и прости числа - задачи с решения

Решение:
При [tex]n\ge 5[/tex] произведението [tex]n!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot \ldots\cdot n[/tex] съдържа множителите [tex]2[/tex] и [tex]5[/tex], затова се дели на [tex]10[/tex] и завършва на [tex]0[/tex]. Следователно събираемите от [tex]5![/tex] до [tex]2018![/tex] не влияят на последната цифра на [tex]P[/tex] и тя съвпада с последната цифра на сбора
[tex]1!+2!+3!+4!=1+2+6+24=33[/tex]
И така, последната цифра на [tex]P[/tex] е [tex]3[/tex].

Решение:
Последната цифра на произведение зависи само от последните цифри на множителите, затова [tex]237^{127}[/tex] завършва на същата цифра като [tex]7^{127}[/tex]. Първите степени на [tex]7[/tex] са
[tex]7^1=7,\quad 7^2=49,\quad 7^3=343,\quad 7^4=2401[/tex]
Последните им цифри са [tex]7[/tex], [tex]9[/tex], [tex]3[/tex], [tex]1[/tex], след което се повтарят с период [tex]4[/tex], защото при умножаване на число, завършващо на [tex]1[/tex], по [tex]7[/tex] отново се получава число, завършващо на [tex]7[/tex]. Тъй като [tex]127=4\cdot 31+3[/tex], то
[tex]7^{127}=\left(7^4\right)^{31}\cdot 7^3[/tex]
Множителят [tex]\left(7^4\right)^{31}[/tex] завършва на [tex]1[/tex], а [tex]7^3=343[/tex] завършва на [tex]3[/tex], следователно [tex]7^{127}[/tex] завършва на [tex]3[/tex]. Последната цифра на [tex]237^{127}[/tex] е [tex]3[/tex].

Решение:
Нека търсеният брой години е [tex]k[/tex]. Днес възрастта [tex]1[/tex] не е просто число, затова [tex]k\ge 1[/tex]. Всички сегашни възрасти са нечетни. Ако [tex]k[/tex] е нечетно, всичките шест нови възрасти са четни, а [tex]3+k\ge 4[/tex] е четно число, по-голямо от [tex]2[/tex], следователно не е просто. Значи [tex]k[/tex] е четно.
При [tex]k=2[/tex] възрастите са [tex]3; 5; 9; 11; 15; 17[/tex], а [tex]9=3\cdot 3[/tex] не е просто число.
При [tex]k=4[/tex] възрастите са [tex]5; 7; 11; 13; 17; 19[/tex] и всички те са прости числа.
Следователно най-малкият брой години е [tex]4[/tex].

Решение:
Изнасяме пред скоби най-малката степен на [tex]3[/tex]:
[tex]3^{2016}+3^{2017}+3^{2019}=3^{2016}\left(1+3+3^{3}\right)=31\cdot 3^{2016}[/tex]
Тъй като [tex]31[/tex] е просто число, всеки делител на числото има вида [tex]3^{k}[/tex] или [tex]31\cdot 3^{k}[/tex], където [tex]0\le k\le 2016[/tex]. Двуцифрените делители от вида [tex]3^{k}[/tex] са [tex]27[/tex] и [tex]81[/tex]. Двуцифрените делители от вида [tex]31\cdot 3^{k}[/tex] са [tex]31[/tex] и [tex]93[/tex], защото още [tex]31\cdot 9=279[/tex] е трицифрено число.
Най-големият от тях е [tex]93[/tex].

Решение:
Страниците са номерирани от [tex]1[/tex], затова всеки лист има нечетна страница от лицевата си страна и следващата четна страница от гърба си. Откъснатата част започва със страница [tex]387[/tex] (нечетна, т.е. лицето на лист) и завършва с гърба на лист, затова последната откъсната страница има четен номер, по-голям от [tex]387[/tex].
Другите числа, записани с цифрите [tex]3[/tex], [tex]8[/tex] и [tex]7[/tex], са [tex]378; 738; 783; 837; 873[/tex]. Числото [tex]378[/tex] е по-малко от [tex]387[/tex], а [tex]783[/tex], [tex]837[/tex], [tex]873[/tex] са нечетни, следователно последната откъсната страница е [tex]738[/tex]. Петър е откъснал всички страници от [tex]387[/tex] до [tex]738[/tex] включително и броят им е
[tex]738-387+1=352[/tex]

Решение:
Записваме числото във вида [tex]a=2007q+99[/tex], където [tex]q\ge 0[/tex] е цяло число. Числата [tex]a[/tex] и [tex]99[/tex] са нечетни, следователно [tex]2007q=a-99[/tex] е четно; тъй като [tex]2007[/tex] е нечетно, [tex]q[/tex] е четно, [tex]q=2s[/tex]. Тогава
[tex]a=4014s+99=18\cdot 223s+18\cdot 5+9=18\left(223s+5\right)+9[/tex]
Тъй като [tex]0\le 9\lt 18[/tex], остатъкът при деление на [tex]a[/tex] на [tex]18[/tex] е [tex]9[/tex].

Решение:
Число с [tex]k[/tex] цифри има сбор на цифрите най-много [tex]9k[/tex], а [tex]9\cdot 223=2007\lt 2015[/tex], следователно числото има поне [tex]224[/tex] цифри. Числа с [tex]224[/tex] цифри и сбор на цифрите [tex]2015[/tex] съществуват (едно е посочено по-долу), а всяко число с повече цифри е по-голямо, затова най-малкото такова число има точно [tex]224[/tex] цифри.
От две числа с еднакъв брой цифри по-малко е това с по-малка първа цифра. Останалите [tex]223[/tex] цифри имат сбор най-много [tex]2007[/tex], затова първата цифра е поне [tex]2015-2007=8[/tex]. Първата цифра е [tex]8[/tex] само ако всички останали [tex]223[/tex] цифри са равни на [tex]9[/tex], което дава точно едно число:
[tex]8\underbrace{99\ldots 9}_{223}[/tex]
Цифрата на единиците му е [tex]9[/tex].

Решение:
Да допуснем противното: всяка от десетте цифри [tex]0; 1; \ldots; 9[/tex] се среща най-много [tex]10[/tex] пъти. Тогава [tex]A[/tex] има най-много [tex]10\cdot 10=100[/tex] цифри. Тъй като [tex]A[/tex] има точно [tex]100[/tex] цифри, достига се равенство, т.е. всяка цифра се среща точно [tex]10[/tex] пъти. Тогава сборът от цифрите на [tex]A[/tex] е
[tex]10\cdot \left(0+1+2+\ldots+9\right)=10\cdot 45=450[/tex]
Този сбор се дели на [tex]3[/tex], следователно по признака за деление на [tex]3[/tex] числото [tex]A[/tex] се дели на [tex]3[/tex]. Но [tex]A=2^{332}[/tex] няма прост делител, различен от [tex]2[/tex] — противоречие. Значи поне една цифра се среща поне [tex]11[/tex] пъти.

Решение:
Нека [tex]p[/tex] е такова просто число. Тъй като [tex]p[/tex] е сбор на две прости числа, [tex]p\ge 2+2=4[/tex], затова [tex]p[/tex] е нечетно и [tex]p\ge 5[/tex]. Сбор на две прости числа е нечетен само ако едното от тях е четното просто число [tex]2[/tex]; следователно [tex]p=q+2[/tex], където [tex]q[/tex] е просто, т.е. [tex]p-2[/tex] е просто число.
От [tex]p=s-t[/tex], където [tex]s[/tex] и [tex]t[/tex] са прости, получаваме [tex]s=p+t\gt p\ge 5[/tex], затова [tex]s[/tex] е нечетно; тогава [tex]t=s-p[/tex] е четно, т.е. [tex]t=2[/tex], и [tex]p+2=s[/tex] е просто число.
И така, [tex]p-2[/tex], [tex]p[/tex] и [tex]p+2[/tex] са прости числа. Тъй като [tex]p-2\equiv p+1\pmod 3[/tex], тези три числа дават при деление на [tex]3[/tex] същите остатъци като последователните числа [tex]p[/tex], [tex]p+1[/tex], [tex]p+2[/tex], т.е. остатъците [tex]0[/tex], [tex]1[/tex] и [tex]2[/tex]. Следователно едно от тях се дели на [tex]3[/tex] и, понеже е просто, е равно на [tex]3[/tex]. Тъй като [tex]p\ge 5[/tex], единствената възможност е [tex]p-2=3[/tex], т.е. [tex]p=5[/tex]. Проверка:
[tex]5=2+3,\quad 5=7-2[/tex]
Значи [tex]5[/tex] е единственото такова просто число.

Решение:
Всяка дроб има вида [tex]\frac{k}{n+k+2}[/tex], където [tex]k=19; 20; \ldots; 91[/tex]. Всеки общ делител на [tex]k[/tex] и [tex]n+k+2[/tex] дели и разликата им [tex]n+2[/tex], и обратно, затова
[tex]\text{НОД}(k; n+k+2)=\text{НОД}(k; n+2)[/tex]
Следователно всички дроби са несъкратими точно когато [tex]n+2[/tex] е взаимно просто с всяко от числата [tex]19; 20; \ldots; 91[/tex].
Нека [tex]p[/tex] е прост делител на [tex]n+2[/tex] (такъв съществува, защото [tex]n+2\ge 3[/tex]). Ако [tex]19\le p\le 91[/tex], то самото [tex]p[/tex] е един от числителите. Ако [tex]p\lt 19[/tex], то сред [tex]73[/tex] последователни числа [tex]19; 20; \ldots; 91[/tex] има кратно на [tex]p[/tex]. И в двата случая някоя от дробите се съкращава на [tex]p[/tex].
Значи всеки прост делител на [tex]n+2[/tex] е по-голям от [tex]91[/tex], а най-малкото просто число, по-голямо от [tex]91[/tex], е [tex]97[/tex]. Затова
[tex]n+2\ge 97\Rightarrow n\ge 95[/tex]
При [tex]n=95[/tex] имаме [tex]n+2=97[/tex] — просто число, което не дели нито едно от числата [tex]19; 20; \ldots; 91[/tex], така че всички дроби са несъкратими. Отговор: [tex]n=95[/tex].