# Prove $c,c^c,c^{c^c},c^{c^{c^c}},\ldots \pmod p$ with $p$ prime has period $1$ or $2$

Suppose $$p$$ is a prime number and $$c$$ is some constant value which is coprime to $$p$$. I found that $$c,c^c,c^{c^c},c^{c^{c^c}},\ldots \bmod p$$ have period $$1$$ or $$2$$.

In other words, it seems sequence,$$(\ ^nc )_{\geq1}$$, have period $$1$$ or $$2$$.

Can we prove this?

The code which I used is here: link

• Are you specifically taking each $a_j$ to be between $0$ and $p$? If $p=3$ and $c=2$ and $a_0=1$, then the $a_n$ alternate back and forth between $2$ and $1$. – Greg Martin Dec 1 '19 at 9:20
• The limit is simply the solution of the problem $c^x\mod (p)=x$ – Uday Khanna Dec 1 '19 at 9:23
• I'm sorry. I specifically choose $a_0=c$ in the code. I change the statement of question now. – ueir Dec 1 '19 at 9:36
• In the example Mindlack provides even with $a_{0}=c=3$ we don't have a solution. I see it as a problem of fixed points, you could even reinterpret it as a problem in Group theory by considering then as permutations if you don't want to apply number theory. – Uday Khanna Dec 1 '19 at 9:37
• Maybe you could provide the numerical data you were dealing with. – Uday Khanna Dec 1 '19 at 9:40

update
If you actually wanted to prove that $$\,^nc \pmod p$$ converge to a constant sequence then the following might help for a proof:

assume $$p=7$$, $$c=5$$
Then what you ask for is whether $$\{5, 5^5 , 5^{5^5}, ...\} \pmod 7$$ converge to a constant sequence.
This is a question of recursive application of "order of cyclic subgroup" :

• we know $$5^k \pmod 7= 5 ^ { k \pmod {\varphi(7)}}\pmod 7= 5 ^ { k \pmod 6}\pmod 7$$
• Now if $$k$$ is itself a power of $$5$$ then we ask furtherly for the residues of $$k=5^j \pmod 6$$.
• we find that this is $$5^{j \pmod 2} \pmod 6$$
• And one step higher this becomes a constant sequence.

Here it is surely meaningful to try a proof. (I think, this should be easy to derive one from that example)

## old version (removed. You can see it in the "edit-history")

• This answer seems to show that the sequence is eventually constant. – pregunton Dec 1 '19 at 10:31
• The key fact is $\phi(p),\phi(\phi(p)),\phi(\phi(\phi(p))),\ldots$ is strictly decreasing sequence until it becomes 1. Then, maybe there is some mistake in the code. Thank you. – ueir Dec 1 '19 at 10:35
• @pregunton - a very nice answer you've found! Perhaps it could be a bit shaped (upps my comment crossed with that last one of ueir) – Gottfried Helms Dec 1 '19 at 10:36

That’s false. Consider $$c=3$$ and $$p=7$$. Note that $$c^2=2$$, $$c^4=4$$ mod $$7$$. So depending on the value of $$a_0$$, you can have two constant sequences. Worse: with $$a_0=3$$, the sequence is a cycle $$3,6,1,3,6,1,\ldots$$.

• I'm sorry. I specifically choose $a_0=c$ in the code. I change the statement of question now. – ueir Dec 1 '19 at 9:36