Dělitelnost

Přeji pěkné odpoledne,

při řešení takového problému si můžeme vypomoci následující větou:

Ať $n > 1$ je přirozené číslo s následujícím prvočíselným rozkladem

$n = \prod_{ i = 1} ^\infty p_i^{ a_i}$,

kde $p_i \in \mathbb{ N}$ je $i$-té nejmenší prvočíslo a pro každé $i \in \mathbb{ N}$ platí, že $a_i \in \mathbb{ N} \cup\ ${ $0$} . Potom počet všech dělitelů čísla $n$ je roven

$\prod_{ i = 1} ^\infty (a_i + 1).$

Jinak řečeno, pokud známe prvočíselný rozklad vstupního čísla (v našem případě $3^2 \cdot 7^4$), pak počet všech dělitelů tohoto čísla je roven součinu uvedených exponentů zvýšených o $1$. V našem případě má tedy číslo $3^2 \cdot 7^4$ právě $(2 + 1) \cdot (4 + 1) = 15$ dělitelů.

Ověřit si to můžeme naivním výčtem dělitelů: $1, 3, 7, 9, 21, 49, 63, 147, 343, 441, 1029, 2401, 3087, 7203, 21609$, kterých je skutečně $15$.

Nyní můžeme velmi jednoduše odpovědět na uvedené otázky:

a) ne

b) ano

c) $120 = 2^3 \cdot 3 \cdot 5$, tj. $(3 + 1) \cdot (1 + 1) \cdot (1 + 1) = 16$ dělitelů, tedy ano

d) Aby mělo číslo právě $15$ dělitelů, musí být jeho prvočíselný rozklad zřejmě zapsatelný ve tvaru $p^{ 14}$ nebo $p'^2 \cdot p''^4$, kde $p, p', p''$ jsou nějaká prvočísla. Jiná varianta není vzhledem k podobě prvočíselného rozkladu čísla $15$ možná. Triviální úvahou dojdeme k tomu, že nejmenší číslo s patnácti děliteli tedy bude $2^4 \cdot 3^2$, nebo $2^{ 14}$. Obě tato čísla jsou vyšší než $120$, odpověď tedy zní ne.

e) Vyjdeme z předchozího bodu. $2^{ 14} < N$, ale $3^{ 14} > N$. Jelikož $2^4 \cdot 29^2 < N$, bude totéž platit pro $2^4 \cdot p^2$, kde $p \in${ $3, 5, 7, 11, 13, 17, 19, 23$} . Máme už tedy $10$ čísel splňujících danou podmínku. Další hodnota $3^4 \cdot 2^2$ nám umožňuje odpovědět ne.

Snad je to takto srozumitelné. Určitě se ozvěte, pokud ne.

Jen upřesním svůj argument z bodu d) - prvočísla $p'$ a $p''$ musí být různá.