Let $m$ be a positive integer. The positive integer $a$ is called a golden residue modulo $m$ if $\gcd(a,m)=1$ and $x^x \equiv a \pmod m$ has a solution for $x$. Given a positive integer $n$, suppose that $a$ is a golden residue modulo $n^n$. Show that $a$ is also a golden residue modulo $n^{n^n}$. Proposed by Mahyar Sefidgaran
Problem
Source: Iran MO 3rd round 2016 mid-terms - Number Theory P3
Tags: number theory, modular arithmetic, Iran
angiland
07.09.2016 04:27
Let $p_1 < p_2 < \dots < p_m$ be the distinct prime factors of $n$. We shall prove the following claim: suppose there exists positive integer $x$ such that $x^x \equiv a \pmod{p_1^{r} p_2^{r} \cdots p_m^{r}}$, with $p_1^{r} \geq p_m$, then there exists positive integer $y$ such that $y^y \equiv a \pmod{p_1^{r + 1} \cdots p_m^{r +1}}$. Assuming the truth of this claim, the condition of the problem yields $r \geq n$ . Thus by iteratively applying the claim we can find an integer $z$ with $z^z \equiv a \pmod{p_1^Np_2^N \cdots p_m^N}$. By choosing $N$ sufficiently large we obtain $z^z \equiv a \pmod{n^{n^n}}$, as desired. It remains to prove the claim. Let $D$ be the least common multiple of $\{(p_{i}-1)p_i^{r}: 1\leq i \leq m\}$. Choose $y = x + kD$, then $y^y = (x + kD)^x \cdot (x + kD)^{kD}$. By Euler's theorem, $(x + kD)^{kD} \equiv 1 \pmod {p_1^{r + 1} \cdots p_m^{r+1}}$. Moreover, since $p_1^{r + 1} \cdots p_m^{r+1} | D^2$, by the binomial theorem we have $$(x + kD)^x \equiv x^x(1+kD) \pmod {p_1^{r + 1} \cdots p_m^{r+1}}.$$Thus we need to find $k$ such that $x^x(1+kD) \equiv a \pmod{p_1^{r + 1} \cdots p_m^{r+1}}$. Let $Q = p_1 p_2 \cdots p_m$, then from hypothesis we have $x^x = a + t \cdot Q^r$. Furthermore, by the definition of $D$ and the assumption that $p_i - 1 < p_m \leq p_j^{r}$, we have $D = u \cdot Q^r$ with $(u, Q) = 1$. Thus $x^x(1+kD) = a + (a\cdot u \cdot k + t)Q^r + (t \cdot u \cdot k) Q^{2r}$. It thus suffices to take $k$ so that $Q | a\cdot u \cdot k + t$, which is possible because both $a$ and $u$ are co-prime with $Q$. The claim is proven and so is the problem.
Achillys
14.04.2017 07:12
angiland wrote: Furthermore, by the definition of $D$ and the assumption that $p_i - 1 < p_m \leq p_j^{r}$, we have $D = u \cdot Q^r$ with $(u, Q) = 1$. Isn't it possible that $\exists$ $i, j$ such that $p_i | p_j - 1$ so that $p_i | (u,Q)$?
angiland
16.04.2017 05:17
The point is that $D$ is divisible by $p_i^r$ but not $p_i^{r+1}$.
Achillys
16.04.2017 12:52
Suppose $n = 30$. Then $D = 60$ while $\phi (900) = 240$, which does not divide $D$. So the relation $(x+kD)^{kD}$ is not necessarily $1 \mod Q^{r+1}$
angiland
17.04.2017 00:41
Try applying Euler's theorem to each prime power, separately.
MarkBcc168
19.09.2017 13:19
I was playing around this problem and was able to prove the following stronger version. Quote: For every positive integer $a,n$ such that $\gcd(a,n)=1$, there exists a positive integer $x$ such that $x^x\equiv a\pmod n$
We will prove the following even stronger claim by induction on $n$.
Quote:
For every positive integer $a,n$ such that $\gcd(a,n)=1$, there exists a positive integer $x$ such that $\gcd(x,\mathrm{lcm}(n,\varphi(n)))=1$ and $x^x\equiv a\pmod n$
Let $p$ be the largest prime divisor of $n$, set $n=p^t\cdot m$ where $p\nmid m$, $d=\mathrm{lcm}(m,\varphi(m))$ and observe that $\gcd(p,d)=1$.
By induction hypothesis, there exists a positive integer $b$ such that $\gcd(b,d)=1$ and $b^b\equiv a\pmod m$. Let $c$ be a positive integer such that $c\equiv b\pmod{d}$ and $\gcd(c,p-1)=1$. Note that $c^c\equiv b^b\equiv a\pmod m$.
Our strategy is constructing a sequence $x_1,x_2,...,x_t$ such that $x_i^{x_i}\equiv a\pmod{p^i\cdot m}$. To construct $x_1$, we need the following lemma.
Lemma : Let $p$ be a prime and $n$ be a positive integer such that $\gcd(n,p-1)=1$. Then the set $\{1^n,2^n,...,p^n\}$ form a complete residue system modulo $p$.
Proof : Obviously $r^n\equiv 0\pmod p\iff r\equiv 0\pmod p$. Suppose that $r^n\equiv s^n\pmod p$ where $p\nmid r,s$. Since $r^{p-1}\equiv s^{p-1}\pmod p$, by order we have $r^{\gcd(n,p-1)}\equiv s^{\gcd(n,p-1)}\pmod p$ $\implies r\equiv s\pmod p$ and we are done. $\blacksquare$.
Now since $\gcd(c,p-1)=1$, we let $x_1$ be the positive integer such that
\begin{align*}x_1&\equiv c\pmod{(p-1)d}\\
(x_1)^c &\equiv a\pmod p
\end{align*}(it exists because CRT). Since $x_1\equiv c\pmod d$, $(x_1)^{x_1}\equiv c^c\equiv a\pmod m$. But $(x_1)^{x_1}\equiv (x_1)^c\equiv a\pmod p$. Note that from our construction, it is clear that $\gcd(x_1,p(p-1)d)=1\implies \gcd(x_1,\mathrm{lcm}(\varphi(pm),pm))=1$.
Now we have to build $x_2, x_3,..., x_t$ using similar trick to Hensel's Lemma. Suppose we know $x_i$, define $x_{i+1}$ by
\begin{align*}x_{i+1}&\equiv x_i+k\cdot p^i \pmod{p^{i+1}}\\
x_{i+1} &\equiv x_i \pmod{p^{i}(p-1)d}\end{align*}for a suitable positive integer $k$. There exist such $k$ if and only if.
\begin{align*}(x_i+k\cdot p^i)^{x_i}\equiv a\pmod{p^{i+1}} &\iff (x_i)^{x_i}+\binom{x_i}{1} (x_i)^{x_i-1}k \cdot p^i \equiv a \pmod{p^{i+1}}\\
&\iff (x_i)^{x_i}(1+k\cdot p^{i-1})\equiv a\pmod{p^{i+1}}\\
&\iff \gcd(p^{i-1},p^{i})\mid (x_i)^{x_i}-a\end{align*}which is true. Finally, note that $\mathrm{lcm}(\varphi(p^{i+1} m), p^{i+1}m)=\mathrm{lcm}(p^{i}(p-1)\varphi(m),p^{i+1}m)\mid p^{i+1}\cdot \mathrm{lcm}(p-1,d)$ and $p\nmid x_i$ for every $i\in\mathbb{N}$. Hence our $\gcd$ condition is preserved while building $x_1,x_2,...$ so we can continue the process of induction and we are done.
Loppukilpailija
23.12.2018 17:20
Quote: Let $p$ be the largest prime divisor of $n$, set $n=p^t\cdot m$ where $p\nmid m$, $d=\mathrm{lcm}(m,\varphi(m))$ and observe that $\gcd(p,d)=1$. By induction hypothesis, there exists a positive integer $b$ such that $\gcd(b,d)=1$ and $b^b\equiv a\pmod m$. Let $c$ be a positive integer such that $c\equiv b\pmod{d}$ and $\gcd(c,p-1)=1$. Note that $c^c\equiv b^b\equiv a\pmod m$. In the above solution, why can we choose $c$ to be such that $c \equiv b \pmod{d}$ and $\gcd(c, p-1) = 1$? We do have the condition $\gcd(p, d) = 1$, but I do not see why we should have $\gcd(d, p-1) = 1$. Why couldn't we have $\gcd(d, p-1, b) > 1$, so that for all $c$ such that $c \equiv b \pmod{d}$ we have $\gcd(c, p-1) > 1$?
MarkBcc168
23.12.2018 17:37
Because the induction hypothesis implies $\gcd(b,d)=1$.
Sprites
01.11.2021 08:21
Generalized version wrote: For every positive integer $a,n$ such that $\gcd(a,n)=1$, there exists a positive integer $x$ such that $x^x\equiv a\pmod n$ Lemma #1:- For any $m \in \mathbb{Z}$ if $\gcd(\varphi(n),m)=1$ then $1^m,2^m,3^m,............,(n-1)^m$ cover a full-residue class modulo $n$ Proof:- This is rather trival;if $r^m \equiv s^m \pmod {p|n}$ then by order-properties we get $r^{\gcd(p-1,m)=1} \equiv s^{\gcd(p-1,m)=1} \pmod p$ and we conclude by CRT. For each $m \in [\mathbb{F}_p]$ define $$\delta(m):=\{m+p,m+2p,m+3p,...............,m+p^2 \} \pmod {\varphi(p)=p-1}$$Consider all pairs of equations $x^{m_1} \equiv a \pmod p$ where $m_1 \in \delta(x)$;clearly all such $x$ work and once we have obtained all pairs $x_1,x_2,...........,x_{w(n)}$ we use Hensel's Lemma to lift these solutions up to $p^{\nu_p(n)}$ and finish by CRT.
Watsoon
18.04.2022 09:05
Can you give some details ? Thanks !
Watsoon
01.05.2022 12:19
MarkBcc168 wrote: Let $c$ be a positive integer such that $c\equiv b\pmod{d}$ and $\gcd(c,p-1)=1$ Are you using Dirichlet's theorem?
lagrange001
10.03.2023 01:20
MarkBcc168 wrote: Because the induction hypothesis implies $\gcd(b,d)=1$. 素数的版本在中国比赛2017北大金秋营中出现过，你能用CRT把它们拼起来吗？