# How does one prove that a natural number $x$ does not generate the multiplicative group of integers mod $4nx - 1$?

How does one prove that a natural number $x$ does not generate the multiplicative group of integers mod $4nx - 1$, where $n$ is any natural number?

I'm stuck on how to prove this, but I'll say what I know. I asked a similar, more specific question a few days ago, and it was resolved by the fact that 4 is a square. However, in this case, the fact that 4 is a square is not enough. If we replace 4 with 9, for instance, then the statement is not true, because $<3>$ generates $\textbf{Z}_{53}$, and $53 = 9*2*3 - 1$.

It's also not the case that $x$ is a square number all the time. In $\textbf{Z}_{39}$, where $39 = 4 * 5 * 2 - 1$, 2 is not a square, but 2 does not generate $\textbf{Z}_{39}$.

Any help or hints would be appreciated. Thank you.

• I don't understand. $2$ and $39 = 4*5*2-1$ are relatively prime, but $2$ does not generate the whole multiplicative group $\textbf{Z}_{39}$. – Peter Bradshaw Jan 2 '17 at 3:04
• Testing if square is definitely the way to go. If $n = 1$ then easily $x = (2x-1)^2$. For larger $n$ quad reciprocity seems easier – user6246 Jan 2 '17 at 4:03

The only way this could happen is if $4nx - 1 = p^e$ is a prime power (and $e$ must be odd, since $4nx - 1 \equiv 3 (4)$. Otherwise the units mod $4nx-1$ are not even cyclic.
If $x$ were to generate the units mod $p^e$ then it would also generate the units mod $p$.
Assume $x$ is odd; then it can't do that because $$\Big( \frac{x}{p}\Big)^e = \Big( \frac{x}{4nx - 1} \Big) = (-1)^{(x-1)/2}\Big( \frac{4nx-1}{x} \Big) = (-1)^{(x-1)/2}\Big( \frac{-1}{x} \Big) = 1$$ using quadratic reciprocity for the Jacobi symbol. So $x$ is always a square mod $p$.
When $x$ is even, you need to include the supplement $$\Big( \frac{2}{4nx-1} \Big) = 1,$$ since $4xn - 1 \equiv 7$ mod $8$.