Modulární aritmetika - zajímavý příklad

Michale, trvalo mi asi 10 sekund to vyřešit a stačily mi znalosti ze základní školy, stačí to jako nápověda?

No to teda nevím. u(3) je dělitelné třemi, u(9) devíti, chtělo by se říct že u(3^n) je dělitelné 3^n, ale nějak nejsem schopný to udolat indukcí.

K formálnímu důkazu ti stačí

$u(3^n) = u(3^{ n-1} )10^{ 2l} + u(3^{ n-1} )*10^l + u(3^{ n-1} ) = u(3^{ n-1} )(10^{ 2l} + 10^l + 1)$

Závorka je dělitelná třemi a tím pádem je splněna indukční hypotéza.

Zdravím,

ono se to dá dokázat i bez matematické indukce. Stačí předpokládat, že existuje nějaké největší $n_{ max}$, pro které to platí (tj. $n_{ max} |u(n_{ max} )$ ), a pak se podívat na číslo $u(3n_{ max} )$. Vidíme, že je dělitelné třemi a současně je dělitelné $u(n_{ max} )$, což je spor s předpokladm.