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.

  • $\begingroup$ 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}$. $\endgroup$ – Peter Bradshaw Jan 2 '17 at 3:04
  • $\begingroup$ 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 $\endgroup$ – 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$.

  • $\begingroup$ Thank you. Do you have any recommendations for where I can learn more about using the Jacobi symbol? $\endgroup$ – Peter Bradshaw Jan 2 '17 at 14:53
  • $\begingroup$ @PeterBradshaw Most elementary number theory books but I don't have any off the top of my head. The Wikipedia page lists the important properties but without proofs. $\endgroup$ – user6246 Jan 3 '17 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.