Делимост и прости числа

1. Съществуване: нека $q$ е най-голямото цяло число, за което $bq \le a$ (то съществува, защото кратните на $b$ растат неограничено в двете посоки). Полагаме $r = a - bq \ge 0$. Ако беше $r \ge b$, то $b(q + 1) \le a$ – противоречие с избора на $q$. Значи $0 \le r < b$.
2. Единственост: ако $a = bq + r = bq_1 + r_1$ с $0 \le r,\ r_1 < b$, то $b(q - q_1) = r_1 - r$. Дясната страна е кратна на $b$, но по модул е по-малка от $b$ – значи е 0. Тогава $r = r_1$ и $q = q_1$.
3. Ако $a = bk$ и $c = bl$, то $a \pm c = b(k \pm l)$ – също кратно на $b$.

∎

1. Записваме числото като $n = 10m + c$, където $c$ е последната цифра. Понеже $2,\ 5$ и $10$ делят $10m$, числото $n$ се дели на тях точно когато се дели $c$.
2. По същия начин $n = 100m + \overline{bc}$ и $100 = 4 \cdot 25$, затова за 4 и 25 решават последните две цифри. А $1000 = 8 \cdot 125$ – за 8 и 125 решават последните три.
3. За 3 и 9: всяко $10^k - 1 = 99\ldots9$ се дели на 9. Затова $$n = a_k 10^k + \ldots + a_1 10 + a_0$$ $$= \left[a_k(10^k - 1) + \ldots + a_1 \cdot 9\right]$$ $$+ (a_k + \ldots + a_0)$$ и $n$ дава същия остатък при деление на 9 (и на 3) като сбора от цифрите си.
4. За 11: при четно $k$ числото $10^k - 1$ се дели на $99 = 9 \cdot 11$, а при нечетно $10^k + 1 = 10(10^{k-1} - 1) + 11$ също се дели на 11. Значи $10^k$ дава остатък $+1$ или $-1$ според четността на $k$, и $n$ дава същия остатък като $a_0 - a_1 + a_2 - \ldots$
5. За 6: ако $n = 2k$ и $3 \mid n$, то $3 \mid 2k$ и $3 \mid 3k$, следователно $3 \mid 3k - 2k = k$ и $6 \mid n$.

∎

1. Съществуване – по индукция: ако $n$ е просто, готово. Иначе $n = ab$ с $1 < a,\ b < n$, а за по-малките числа $a$ и $b$ разлагането вече съществува – слепваме двете разлагания.
2. Ключът към единствеността е лемата на Евклид: ако простото $p$ дели $ab$, то $p \mid a$ или $p \mid b$. Тя се доказва с тъждеството на Безу (виж урока „НОД и НОК“): ако $p \nmid a$, то $\text{НОД}(a,\ p) = 1$ и $ax + py = 1$ за някои цели $x,\ y$. Умножаваме по $b$: $abx + pby = b$ – двете събираеми се делят на $p$, значи и $b$.
3. Единственост: нека $p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l$ са две разлагания (простите могат да се повтарят). По лемата $p_1$ дели някое $q_j$, а щом $q_j$ е просто, $p_1 = q_j$. Съкращаваме го от двете страни и повтаряме – множителите се изчерпват едновременно и двете разлагания съвпадат.
4. Лемата не е очевидна: например сред четните числа $2, 4, 6, \ldots$ „неразложими“ са 2, 6, 10, 14, 18, … и $36 = 6 \cdot 6 = 2 \cdot 18$ – разлагането не е единствено.

∎

1. Ако $d \mid n$, то $n = d \cdot e$. Разлагаме $d$ и $e$ на прости множители – заедно те дават разлагането на $n$. По единствеността в $d$ участват само $p_1, \ldots, p_k$, и то с показатели $b_i \le a_i$.
2. Обратно, всяко $d = p_1^{b_1} \cdots p_k^{b_k}$ с $0 \le b_i \le a_i$ дели $n$: частното е $p_1^{a_1 - b_1} \cdots p_k^{a_k - b_k}$.
3. Различни избори на показателите дават различни числа (пак по единствеността). За $b_1$ има $a_1 + 1$ възможности, за $b_2$ – $a_2 + 1$ и т.н. По правилото за умножение делителите са $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$.

∎

1. Да допуснем, че простите числа са краен брой: $p_1, p_2, \ldots, p_k$. Разглеждаме $N = p_1 \cdot p_2 \cdots p_k + 1$.
2. При деление на всяко $p_i$ числото $N$ дава остатък 1, т.е. не се дели на никое от тях.
3. $N > 1$ има поне един прост делител – и той не е в списъка. Противоречие, значи простите числа са безброй.

∎