Mocniny

Přeji pěkné odpoledne, Martino,

důležité především je, co je to devítkový zápis čísla.

Jedná se o sumu $\sum_{ i = 0} ^{ n} a_i \cdot 9^i$, kde $n \in \mathbb{ N}$ a $a_i$ je pro každé $i$ vždy nějaké přirozené číslo mezi $0$ a $9$.

Např. číslo $232$ zapíšeme v desítkové soustavě jako

$2 \cdot 10^2 + 3 \cdot 10^1 + 2 \cdot 10^0$,

zatímco v devítkové soustavě jako

$2 \cdot 9^2 + 7 \cdot 9^1 + 7 \cdot 9^0$

V tuto chvíli je potřeba si uvědomit, co bychom obrdželi, pokud by se nám povedlo najít zbytek po dělení zadaného čísla $7^{ 1629}$ číslem $81$. Dostali bychom číslo, které by bylo možné zapsat jako $a_1 \cdot 9^1 + a_0 \cdot 9^0$, což je rozvoj posledních dvou číslic v devítkové soustavě. Jelikož pro $a_0$ a $a_1$ existují striktní omezení, tedy musí to být přirozená čísla mezi $0$ a $9$, bylo by snadné hodnoty $a_1$ a $a_0$ najít. Jejich zřetězení $a_1 \cdot 10^1 + a_0 \cdot 10^0$ by poté bylo řešením vaší úlohy.

Potřebujeme tedy vyřešit rovnici

$7^{ 1629} \equiv a$ $(mod$ $81)$,

kde $a$ je neznámé přirozené číslo mezi $0$ a $80$.

V tuto chvíli můžeme využít Eulerovu větu, která praví, že pokud jsou dvě přirozená čísla $a, n$ nesoudělná, pak v modulární aritmetice $mod$ $n$ platí relace kongruence:

$a^{ \varphi(n)} \equiv 1$ $(mod$ $n$),

kde $\varphi(n)$ je Eulerova funkce.

My víme, že $7$ a $81$ jsou nesoudělná čísla, tedy můžeme psát, že platí relace kongruence:

$7^{ \varphi(81)} \equiv 1$ $(mod$ $81$).

Hodnotu $\varphi(81)$ zde vypočtu pomocí vzorce pro rozklad na prvočíselné dělitele následovně:

$\varphi(81) = 81 \cdot \Big( 1 - \frac{ 1} { 3} \Big) = 54$

Platí tedy:

$7^{ 54} \equiv 1$ $(mod$ $81$).

Nyní je třeba zjistit, kolikrát se $54$ vejde do $1629$.

$\left \lfloor{ \frac{ 1629} { 54} } \right \rfloor \cdot 54 = 1620,$

tedy víme, že

$7^{ 1620} \equiv 1$ $(mod$ $81$).

Proto nám zbývá vyřešit rovnici

$7^{ 9} \equiv a$ $(mod$ $81)$,

Zde už snadno vypočítáme, že $a = 55$.

Můžeme tedy psát $55 = a_1 \cdot 9^1 + a_0 \cdot 9^0$

Je zřejmé, že $a_1$ zde bude výsledek celočíselného dělení $55$ číslem $9$ a $a_0$ příslušný zbytek.

Platí tedy $a_1 = 6, a_0 = 1$.

Zjistili jsme tedy, že poslední dvě číslice čísla $7^{ 1629}$ v devítkové soustavě jsou $61$.

Snad je to srozumitelné! Určitě se ozvěte, pokud je něco nejasné.

Ďakujem, moc ste mi pomohli, myslím, že teraz to už zvládnem.