Did I prove $\;{^{n}2} \equiv {^{n-1}2} $ $\,$ mod $n\;\;\;$ for $\;n \geq 2\;$?

Question

Let's first state some properties of tetrations:

• They are one of the basic arithmetic functions, 4. hyperoperation to be exact.
  • $\;{^{n}2}$ is in its basic, most elemental form. So we can't really simplify it or break it down.
• Tetrations also aren't associative, the "agreement" is that we exponentiate from right-to-left.
  • So e.g. $\; 2^{2^{2^{2}}} = 2^{(2^{(2^{2})})}=2^{(2^{4})}=2^{(16)}=65,536 $
  • Not e.g. $\; 2^{2^{2^{2}}} = ((2^{2)^{2)^{2}}}=(4^{2)^{2}}=16^{2}=256 $

I stated these properties, because when I first started dealing with this problem, I had no idea that a thing like tetrations exists and did a lot of unnecessary work and faulty adjustments.

The idea that helped me, hopefully, prove it came with the use of modular exponentiation.

Modular exponentiation

• $a^b\;$ mod $c \; \equiv \; ((a \;$ mod $c)^b)\;$mod $c$
• Often used to calculate mod for large values of $b$, which is exactly what I had to deal with.

The use of it, illustrated by an example:

For $n=5 : \; {^{n}2} ={2^{2^{16}}}=2^{65536}$

Mod for ${^{n}2}$ : $\;{2^{2^{16}}}$ mod $5=\;{4^{2^{15}}}$ mod $5=\;{16^{2^{14}}}$ mod $5=\;{1^{2^{14}}}$ mod $5=\;1$

Mod for ${^{n-1}2}$ : $\;{2^{2^{4}}}$ mod $5=\;{4^{2^{3}}}$ mod $5=\;{16^{2^{2}}}$ mod $5=\;{1^{2^{2}}}$ mod $5=\;1$

So generally: $\;{2^{2^{n}}} =\;{4^{2^{n-1}}}=\;{16^{2^{n-2}}}\;$ ...and so on, until the basis is big enough to use mod

Now from what I can tell, there are two or three scenarios depending on how you look at it.

• Stable and decisive results, such as $1$ or $0$ where, the function ends
  • E.g. $n = 5\;$ so ${^{5}2}$ mod $5=1\;$ and $n = 8\;$ so ${^{8}2}$ mod $8=0$
• Stable results, where if you square it and then subtract the mod, you'll land again on the same number
  • E.g. $n = 6\;$ so ${^{6}2}$ mod $6=4\;$ and E.g. $n = 10\;$ so ${^{10}2}$ mod $10=6\;$
• Looping/recurring results, that again will trap the function
  • E.g. $n = 7\;$ so ${^{7}2}$ mod $7= 2\; or \;4\;$ and $n = 11\;$ so ${^{11}2}$ mod $11= 4\; or\; 5\; or\; 3\; or \;9$

From the three, the only one that could cause trouble, would be the looping one. The worry could be that the result will land on a different number for $\;{^{n}2}\;$ and $\;{^{n-1}2}$

But $\;{^{n}2}\;$ goes through the same proces as $\;{^{n-1}2}$ just twice.

$\;{^{n-1}2}$ will finish first, but the result won't be changed while $\;{^{n}2}\;$ does the "x more laps" because it will be out of exponents to get it into the loop again and since the $\;{^{n}2}\;$ has exactly x times the exponents it will finish on the same result out of the loop.

This bit was a bit informal, but I'm not sure how to write it down properly.

Let's for take $n=5\;$ again

For $\;{^{n}2}\; = {2^{2^{16}}}=2^{65536}$

For $\;{^{n-1}2}\; = {2^{2^{4}}} =2^{16} $

And since $\;65536 = 2^{16}\;$ is of course divisible by $\;16 = 2^{4}\;$ it makes sense, that they'll meet at the same result.

Does it make sense ? Are there any gaps, that I forgot to cover ? Did I actually prove it ?

I'm well aware that, my method and my record of it is far from optimal. If you have any suggestions on how to write it more formally and correctly, please tell me.

Thanks a lot, any sort of advice and help is appreciated.

Czech version (needed it for my homework sorry):

Dokaž $\;{^{n}2} \equiv {^{n-1}2} $ $\,$ mod $n\;\;\;$ for $\;n \geq 2\;$

Jde o Tetratace

Důležité vlastnosti tetratace:

• Jde o základní aritmetickou operaci. Konkrétně 4. Hyperoperaci.

  • $\;{^{n}2}$ je poměrně jednoduchá operace co se tetrací týče. Tedy je ve své základní, nejvíce elementární formě. Takže jí upravit, zjednodušit už moc nemůžeme.

• Tetratace nejsou asociativní. Záleží z jakého směru exponujeme, jako standart se bere z prava do leve, nebo-li zhora dolů.

  • Tedy e.g. $\; 2^{2^{2^{2}}} = 2^{(2^{(2^{2})})}=2^{(2^{4})}=2^{(16)}=65,536 $
  • Ne e.g. $\; 2^{2^{2^{2}}} = ((2^{2)^{2)^{2}}}=(4^{2)^{2}}=16^{2}=256 $

Tyto vlastnosti jsem uvedl, protože když jsem tento problém začal řešit, tak jsem nevěděl, že tetratace existují a kvůli neznalosti jejich vlastností jsem si nadělal spoustu zbytečné práce a nadělal spoustu chybných úprav ve snaze tvar zjednodušit.

Myšlenka která mi pomohla problém dokázat, byla skrytá v Modulárním umocňování

Modulárním umocňování

• $a^b\;$ mod $c \; \equiv \; ((a \;$ mod $c)^b)\;$mod $c$
• Často používané na počítání modula pro velké čísla, exponenty $b$, což je přesně případ se kterým se potýkáme u této úlohy.

Její použití illustruji na případu:

Pro $n=5 : \; {^{n}2} ={2^{2^{16}}}=2^{65536}$

Mod pro ${^{n}2}$ : $\;{2^{2^{16}}}$ mod $5=\;{4^{2^{15}}}$ mod $5=\;{16^{2^{14}}}$ mod $5=\;{1^{2^{14}}}$ mod $5=\;1$

Mod pro ${^{n-1}2}$ : $\;{2^{2^{4}}}$ mod $5=\;{4^{2^{3}}}$ mod $5=\;{16^{2^{2}}}$ mod $5=\;{1^{2^{2}}}$ mod $5=\;1$

Takže obecně: $\;{2^{2^{n}}} =\;{4^{2^{n-1}}}=\;{16^{2^{n-2}}}\;$ ...a takhle dál, dokud základ není dostatečně velký na to aby jsme použili modulo.

Výsledky $\;{^{n}2}$ mod $n\;$ různých $\;n\;$ můžeme rozdělit do dvou či tří kategorii.

• Stabilní a konečné výsledky, tedy $1$ nebo $0$ kde, funkce skončí
  • E.g. $n = 5\;$ takže ${^{5}2}$ mod $5=1\;$ a $n = 8\;$ takže ${^{8}2}$ mod $8=0$
• Stabilní výsledky, které po mocnění dvojkou a odečtení modula, skončí zpět na čísle které jsme umocňovali, tedy funkci uvězní v smyčce o jedné otáčce.
  • E.g. $n = 6\;$ takže ${^{6}2}$ mod $6=4\;$ a E.g. $n = 10\;$ takže ${^{10}2}$ mod $10=6\;$
• Opakující se výsledky, tedy smyčka o více otáčkách, které funkci také uvězní.
  • E.g. $n = 7\;$ takže ${^{7}2}$ mod $7= 2\; nebo \;4\;$ a $n = 11\;$ takže ${^{11}2}$ mod $11= 4\; nebo\; 5\; nebo\; 3\; nebo \;9$

Z těchto tří kategorií výsledků, jediná která by mohla tvrzení vyvrátit, jsou opakující se výsledky. Zdá se, že by problém mohl nastat kdyby funkce $\;{^{n}2}\;$ a $\;{^{n-1}2}$ skončily na různých číslech smyčky.

Ale stačí si uvědomit, že $\;{^{n}2}\;$ prochází stejným procesem jako $\;{^{n-1}2}$ jen vícekrát.

$\;{^{n-1}2}$ sice skončí první, ale její výsledek se nezmění už nezmění a počká, než $\;{^{n}2}\;$ také doběhne. Použil jsem analogii s okruhy, jako na běžecké trati, obě funkce mají stejný cíl, v oku matematiky tedy i start. Funkce$\;{^{n}2}\;$ jen běží více okruhů a to přesně $x$krát. Má více exponentů na to aby proběhla víckrát.

Uznávám, že tento segment byl poměrně dost neformální, ale pro mě to byla užitečná vizualizace. Také jsem si nebyl jistý jak to formálně zapsat.

Pro přesnost ukáži na příkladě:

Vezmeme si $n=5\;$

Pro $\;{^{n}2}\; = {2^{2^{16}}}=2^{65536}$

Pro $\;{^{n-1}2}\; = {2^{2^{4}}} =2^{16} $

A protože $\;65536 = 2^{16}\;$ je jasně dělitelné $\;16 = 2^{4}\;$ dává smysl, že dopadnou na stejný výsledek. $\;{^{n}2}\;$ akorát udělá $\;65536 \, : \, 16 \,=\, 4096 \,= \,2^{12}\; $ více kol.

FJFI DIM1