$\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$

elementary-number-theorynumber theory

Fix an integer $a$, and a prime $p$.

Define
$$S(a,p)=\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$$
to be the set of all integers $x\in\{0,…,p-1\}$ such that, for some positive integer $n$,
$$x\equiv \sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a+x}}}}\;\;(\text{mod}\;p)$$
with exactly $n$ radicals, and where each square root evaluates to a valid modular square root.

Some examples:
\begin{align*}
S(2,29)&=\{2,3,4,5,7,14,18,20,21,23,28\}\\[4pt]
S(3,11)&=\{0,1,6,8,9\}\\[4pt]
S(4,23)&=\{0,2,8,12,14,19\}\\[4pt]
S(5,7)&=\{4\}\\[4pt]
\end{align*}
Based on sample data, I'll pose two conjectures . . .

Conjecture $(1)$:

$\qquad$$S(a,p)\ne{\large{\varnothing}}$, for all $a,p$.

Conjecture $(2)$:

$\qquad$If $x\in S(a,p)$, then $x$ satisfies
$$x\equiv \sqrt{a+\sqrt{a+\sqrt{a+\cdots + \sqrt{a+x}}}}\;\;(\text{mod}\;p)$$
$\qquad$with at most $p-1$ radicals.

Questions:

  • Can someone prove or disprove either of the conjectures?$\\[4pt]$
  • Short of that, is there some intuition for or against either of the conjectures?

Update:

I'm no longer sure about conjecture $(1)$ since it was based on flawed sample data.

Also, as noted in the comments, conjecture $(2)$ only holds for odd primes $p$, but the upper bound is too high.

I had a bug in my program — sorry for the mistakes.

I think the idea of iterated modular square roots has potential for some interesting explorations, so I'll leave the question for now.

Hopefully after I correct my program, I'll be able to pose revised conjectures that are consistent with sample data.

Update #$2$:

Ok, my program is now corrected.

Conjecture $(1)$ looks good, but I see it's now been proved.

As previously noted, assuming $p$ is odd, conjecture $(2)$, while true, is too weak.

Thanks to everyone for the comments and answers.

Best Answer

let $f_{a,p} : \Bbb Z/p\Bbb Z \to \Bbb Z/p\Bbb Z $ given by $f(x) = x^2-a$.
Then $x \in S(a,p)$ if and only if there is some $n$ such that $f_{a,p}^{\circ n}(x) = x$,.

Draw a graph where the vertices are the elements of $\Bbb Z/p\Bbb Z$ and where there is an arrow from $x$ to $f_{a,p}(x)$. Then $S(a,p)$ is the set of vertives that are parts of cycles.

Iterating $f_{a,p}$ on any element eventually ends up in a cycle, so $S_{a,p}$ is non empty.

If $p=2$ then $S(a,p)$ is a bijection so every element is part of a cycle.

If $p \neq 2$, then every element $x \neq -a$ has either $0$ or $2$ preimages $y_1,y_2$, and only one of them can be part of a cycle (since $x$ can only appear once in the cycle it will have either $\ldots \to y_1 \to x \to \ldots$ or $\ldots \to y_2 \to x \to \ldots$), so $S(a,p)$ has at most $(p+1)/2$ elements (and so the cycle lengths can be at most $(p+1)/2$)

Related Question