10. Koniec Mikroténovým Sáčkom! vzorové riešenie

Označme si \(V=10^{10^{10^n}}+10^{10^n}+10^n-1\). Ak chceme ukázať, že \(V\) nie je prvočíslo, tak ako jednoduché spôsoby sa nám priamo núkajú rozloženie na súčin a nájdenie deliteľa.

Nájsť deliteľa znamená pre dané \(n\) nájsť \(d\) také, aby \(10^{10^{10^n}} + 10^{10^n} + 10^n - 1 \equiv 0 \pmod{d}\).¹ Skúsme ho nájsť tak, aby čísla \(10^{10^{10^n}}, 10^{10^n}, 10^n\) mali pekné zvyšky po delení \(d\). Ako vhodní kandidáti sa naskytujú \(d_1=10^k, d_2=10^k+1, d_3=10^k-1\). Zrejme pri deliteľovi \(d_1\) bude mať \(V \pmod{d_1}\) jednotku na mieste jednotiek, teda nevyhovuje.

Pozrime sa na \(d=d_2\). Po troche skúšania môžeme prísť na to, že vieme docieliť, aby zvyšky členov \(V\) boli \(\pm1\). Takto možno zistiť, že pre \(n=2^ab\) (kde \(b\) je nepárne) je \(d=10^{2^a}+1\) je deliteľ \(V\). Inak napísané \(-1 \equiv 10^{2^a} \pmod{d}\). Pozrime sa na zvyšky členov \(V\) po delení \(d\).

• \(-1 \equiv -1 \pmod{d}\).

• \(10^n = 10^{2^ab} = (10^{2^a})^b \equiv (-1)^b \equiv -1 \pmod{d}\).

• \(10^{10^n}= 10^{2^a5^a(10^{n-a})}= (10^{2^a})^{5^a10^{n-a}} \equiv (-1)^{5^n10^{n-a}} = 1 \pmod{d}, \) keďže \(5^n10^{n-a}\) je párne (rozmyslite si).

• \(10^{10^{10^n}} = 10^{2^a5^a(10^{10^n-a})} = (10^{2^a})^{5^a10^{10^n-a}} \equiv (-1)^{5^a10^{10^n-a}} = 1,\) keďže \(5^a10^{10^n-a}\) je párne (rozmyslite si).

Teda \(10^{10^{10^n}}+10^{10^n}+10^n-1 \equiv 1+1-1-1 =0 \pmod{d}\), našli sme teda deliteľa \(d_2\) výrazu \(V\). Keďže \(1<10^{2^a}+1<V\), \(V\) nie je prvočíslo. Týmto je dôkaz hotový.