I have the following conjecture:

Let $p$ be a prime, and $g\in(\Bbb{Z}/p\Bbb{Z})^\times$. If $g$ generates $(\Bbb{Z}/p\Bbb{Z})^\times$, then $g$ also generates $(\Bbb{Z}/p^m\Bbb{Z})^\times$ for all $m\in\Bbb{N}$ with $m>1$.

Now I did attempt a proof, but I can't seem to figure out where to go at the end, or if there's a simpler proof than what I had in mind. Number theory and group theory aren't my strong suits. Here's my proof:

Proof: We will attempt prove this inductively. Assume $g$ generates $(\Bbb{Z}/p^m\Bbb{Z})^\times$. Thus $g^{\phi(p^m)}\equiv 1\ (\text{ mod }p^m)$, where $\phi(n)$ is Euler's totient function. We also know $g^{\phi(p^m)}$ is the smallest power of $g$ that satisfies this congruence. We need to show that the smallest power of $g$ that satisfies $g^k\equiv1\ (\text{ mod }p^{m+1})$ is $k=\phi(p^{m+1})=p^m(p-1)$.

Assume there exists such a $k$ that $g^k\equiv1\ (\text{ mod }p^{m+1})$, with $k\le\phi(p^{m+1})$. We want to show that the only possibility is $k=\phi(p^{m+1})$. By Lagrange's Theorem, $k\ |\ \phi(p^{m+1})$, since otherwise the order of the subgroup generated by $g$ would not divide the order of $(\Bbb{Z}/p^{m+1}\Bbb{Z})^\times$.

We can rewrite these equivalences as follows: $$ 1.\quad \frac{g^{\phi(p^{m+1})}-1}{p^{m+1}}\in\Bbb{N} \\ 2.\quad \frac{g^k-1}{p^{m+1}}\in\Bbb{N} $$

Now, Zsigmondy's Theorem states that if $(a, b)=1$ and $n\in\Bbb{N},\ n>1$, then there exists some prime $p$ that divides $a^n - b^n$ that doesn't divide any $a^k - b^k$ for $k < n$ (with some notable exceptions that we will be careful to avoid in this proof).

By setting $a = g,\ b=1,\ n=\phi(p^{m+1})$, in order to show that $k=\phi(p^{m+1})$ is the only solution, we must show that $g^{\phi(p^{m+1})}-1$ and $g^k - 1$ have all the same prime factors (with different multiplicities), because if this is true, we would be contradicting Zsigmondy's theorem if $k<\phi(p^{m+1})$. Thus $k=\phi(p^{m+1})$.

Currently, I have no clue how to prove that they have the same prime factors of different multiplicities. Write $g^{\phi(p^{m+1})}-1 = Cp^{m+1}$ and $g^k-1 = Dp^{m+1}$ with $C,\ D\in\Bbb{N}^2$. Then it's easy to see that $\frac CD\in\Bbb{N}$, since $$ \begin{align} \frac CD = \frac{g^{\phi(p^{m+1})}-1}{g^k-1} & = \frac{(g^k)^{\phi(p^{m+1})/k}-1}{g^k-1} \\ & = \sum_{j=0}^{\phi(p^{m+1})/k-1}g^{jk} \end{align} $$ and the last sum is a sum of integers (since $k\ |\ \phi(p^{m+1})$). Thus it suffices to show that $\omega\left(g^{\phi(p^{m+1})}-1\right) = \omega\left(g^k-1\right)$, where $\omega(n)$ counts the number of distinct prime factors of $n$.

This is where I'm stuck.

I can't help but think there's a much simpler proof. Also, it concerns me that I haven't used the fact that $g^{\phi(p^m)}\equiv 1(\text{ mod }p^m)$. I feel like if I could figure out how to use that fact, I could avoid the whole Zsigmondy's Theorem rigmarole (that, or I could use it to finish the proof in it's current state). Any ideas?

Also, if possible, can the proof avoid using Sylow Subgroups? I'm looking for a way to prove this without relying on Sylow's Theorems (I wasn't explicitly told that they would help solve this problem, but I have a hunch, since I saw a proof that $(\Bbb{Z}/p\Bbb{Z})^\times$ is cyclic which used Sylow's Theorems).

  • $\begingroup$ Hopefully my memory isn't flawed, but I'm pretty sure you're conjecture isn't true. If $g$ generates $(\mathbb{Z}/p\mathbb{Z})^{\times}$, then one of $g$ or $g+p$ generates $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$. Try to prove that and see if you can get some sort of super-generator using that. $\endgroup$
    – tc1729
    Aug 21 '16 at 22:33

This is an excellent conjecture, and a great attempt at proof. But I think the reason that you may have trouble finishing your proof is that your conjecture is actually false.

For instance, $14$ is a generator of $(\mathbb{Z}/29\mathbb{Z})^\times$, but $14$ is not a generator of $(\mathbb{Z}/29^2\mathbb{Z})^\times$.

But you can show that if $g$ is a generator for $(\mathbb{Z}/p\mathbb{Z})^\times$ then at least one of $g$ or $g + p$ is a generator of $(\mathbb{Z}/p^k\mathbb{Z})^\times$.

  • $\begingroup$ WOW. That is incredibly funny. I thought I was thorough when I was checking the conjecture, but I guess not. Thanks for informing me! $\endgroup$ Aug 21 '16 at 22:38
  • $\begingroup$ @mixedmath, I think your statement might be missing the condition $p \neq 2$, as $(\mathbb Z/2^k \mathbb Z)^{\times}$ isn't even cyclic for $k \geq 3$. $\endgroup$ Aug 22 '16 at 3:38

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.