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á.