Modulární aritmetika - zajímavý příklad
Dobrý den, potřeboval bych nakopnout s následujícím:
Je dána posloupnost u(n)=111111 (n krát) čili u(1)=1, u(2)=11, u(3)=111 apod.
Dokažte, že existuje nekonečno n, pro která u(n) je dělitelné n.
Michal D.
17. 02. 2021 21:40
4 odpovědi
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.