Let $g$ be a Fibonacci primitive root $\pmod{p}$. i.e. $g$ is a primitive root $\pmod{p}$ satisfying $g^2 \equiv g+1\; \pmod{p}$. Prove that $g-1$ is also a primitive root $\pmod{p}$. if $p=4k+3$ then $(g-1)^{2k+3} \equiv g-2 \pmod{p}$, and deduce that $g-2$ is also a primitive root $\pmod{p}$.
Problem
Source:
Tags: modular arithmetic, Primitive Roots
25.05.2007 03:24
a.: We have $(g-1)g=g^2-g \equiv 1 \mod p$, thus $g-1$ is the inverse of $g \mod p$, thus primitive root, too. b.: $g-1$ is a nonsquare $\mod p$ since it's a primitive root. Thus $(g-1)^\frac{p-1}{2} \equiv -1 \mod p$. This gives $(g-1)^{2k+3} = (g-1)^2 \cdot (g-1)^\frac{p-1}{2} \equiv -(g^2-2g+1) \equiv g-2 \mod p$. All we are left to show is $\gcd(2k+3,p-1)=1$, which follows via $\gcd(2k+3, 4k+3) = \gcd(2k+3, -3)=1$, the latter because otherwise $3|p$, impossible.
08.05.2020 21:09
let $g$ be a primitive root of $p$ then we shall assert that $g^{-1}$ is also a primitive root, assume that $(g^{-1})^x \equiv 1 \mod p$ that $x<p-1$ $(g)^x(g^{-1})^x \equiv g^x \equiv 1 \mod p$ which is a contradiction so $x=p-1$ and $g^{-1}$ now $g^2 \equiv g+1 \mod p \implies g(g-1) \equiv 1 \mod p$ so $g-1=g^{-1} \implies$ $g-1$ is a primitive root as well. now we know if $x^2 \equiv 1 \mod p \implies p \mid x+1$ or $p \mid x-1$ now part $b$ we can see that $g^{\frac{p-1}{2}} \equiv -1 \mod p$ $g^{2k+1} \equiv -1 \mod p$ and because $g^{-1}=g-1$ then $(g-1)^{2k+3}=g^{-(2k+3)} =g^{-(2k+1)} \times g^{-2}$ now it's straightforward to prove $-g^{-2} \equiv g-2 \iff -1 \equiv g^3-2g^2 \iff g^3 - 2g^2 +1 = (g-1)(g^2-g-1) \equiv 0$