$p$ is an odd prime number. Prove that there exists a natural number $x$ such that $x$ and $4x$ are both primitive roots modulo $p$. Proposed by Mohammad Gharakhani
Problem
Source: Iran 3rd round 2011-Number Theory exam-P3
Tags: modular arithmetic, number theory proposed, number theory
19.09.2012 23:21
I will generalize this to $x$ and $d^2x$ where $d$ is an integer. Let $g$ be a primitive root modulo $p$. Then we know $d^2 \equiv g^{2k} \pmod{p}$ for some $k$. Now, it suffices to show there exist two integers $a,b$ such that $b-a = 2k$ and that $\gcd(b,p-1) = \gcd(a,p-1) = 1$. This is luckily easy. Let $2,q_1,q_2,...,q_z$ be the prime divisors of $p-1$. Let $2k \equiv a_i \pmod{q_i}$ for each $1 \le i \le z$. Now, choose $a \equiv 1 \pmod{2}$ and $a \equiv -a_i + z_i \pmod{q_i}$ where $z_i$ is some prime, not $q_i$, and $a_i \not \equiv z_i \pmod{q_i}$ which exists by CRT. It is easy to see $\gcd(a,p-1) = 1$ and $\gcd(a+2k, p-1) = 1$. Thus $g^a, g^{a+2k}$ are primitive roots and $g^{a+2k} \equiv d^2g^a \pmod{p}$ so we're done.
30.09.2012 16:13
For an arbitrary integer $a$ it's efficient that we have $a=d^2 (mod p)$for some integer $d$.
16.04.2017 11:28
Lemma:For each number $p^{\alpha}$ and $(x,p)=1$ ,$p\not =2$ we're able to find $(y,p)=1$ so that $(x+y,p)=1$. Proof Suppose not ,than all of the elements $x+y_1,x+y_2,...x+y_{\phi(p^{\alpha}}$ are a subset of group not coprime with $p$.However for $p>2$ we have that $\phi(p^{\alpha})>\frac{p^{\alpha}}{2}$ and hence the desired.$\blacksquare$ Let $p_1,p_2,...p_k$ be the non-even divisors of $p-1$.Let $j$ be the generator of $Z_{\times,p}$ now $j^{2a}=4$.Now from lemma pick $g\equiv y_i\pmod{p_i^{\alpha_i}}$ so that $(2a+y_i,p_i)=1$.From our choice of $g$ is immediate $(g,p-1)=1$ (additionally $g$ is odd) and so $(g+2a,p-1)=1$ and hence $x:=j^g$ satisfies the conditions.$\blacksquare$