1
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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$. $\endgroup$ – Greg Martin Dec 1 '19 at 9:20
  • 1
    $\begingroup$ The limit is simply the solution of the problem $c^x\mod (p)=x$ $\endgroup$ – Uday Khanna Dec 1 '19 at 9:23
  • $\begingroup$ I'm sorry. I specifically choose $a_0=c$ in the code. I change the statement of question now. $\endgroup$ – ueir Dec 1 '19 at 9:36
  • $\begingroup$ 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. $\endgroup$ – Uday Khanna Dec 1 '19 at 9:37
  • $\begingroup$ Maybe you could provide the numerical data you were dealing with. $\endgroup$ – Uday Khanna Dec 1 '19 at 9:40
1
$\begingroup$

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")

$\endgroup$
  • 1
    $\begingroup$ This answer seems to show that the sequence is eventually constant. $\endgroup$ – pregunton Dec 1 '19 at 10:31
  • 2
    $\begingroup$ 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. $\endgroup$ – ueir Dec 1 '19 at 10:35
  • 1
    $\begingroup$ @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) $\endgroup$ – Gottfried Helms Dec 1 '19 at 10:36
2
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.