The unitary group modulo $p$ is also written $(Z/pZ)^*$ and includes the integers $U(p) = \{ 1, 2, …, p - 1 \}$ and is a group under multiplication modulo $p$.

While this is not the exact problem I'm working on, it is most definitely an important piece of a homework problem, so please, hints are prefered.

I have found several proofs of the existence of a primitive root, which show that $U(p)$ is cyclic. However, they all rely on polynomials and field theory. I'm looking for a proof that does not require these subjects. Is one possible? If it's not possible, could someone show why it's not possible?

  • 4
    $\begingroup$ You need to know something about $(\Bbb Z/p\Bbb Z)^*$ in order to prove that it's a cyclic group. What sort of somethings are you willing to entertain? $\endgroup$ – Lord Shark the Unknown Nov 7 '18 at 17:50
  • $\begingroup$ Not quite sure I understand. I guess I'm trying to avoid heavy machinery from other branches of mathematics. You could use Euler's totient function if that helps. But like I said in my OP, field theory and polynomials would be too much. $\endgroup$ – farleyknight Nov 7 '18 at 17:51
  • $\begingroup$ Well the usual something is the fact that a polynomial of degree $n$ over a field has at most $n$ zeros. Is that beyond the pale? $\endgroup$ – Lord Shark the Unknown Nov 7 '18 at 17:56
  • $\begingroup$ Yea, I mentioned that exact theorem to my prof and he said it was off limits. $\endgroup$ – farleyknight Nov 7 '18 at 17:56
  • $\begingroup$ Try this root en.wikipedia.org/wiki/Multiplicative_order, starting from <<As a consequence of Lagrange's theorem, $ord_n(a)$ always divides $\varphi(n)$. If $ord_n(a)$ is actually equal to $\varphi(n)$ ... >> $\endgroup$ – rtybase Nov 7 '18 at 18:02

Consider this lemma, which is pure group theory (*):

Let $G$ be a group of order $m$. If, for every divisor $d$ of $m$, there are no more than $d$ elements of $G$ satisfying $x^d=1$, then $G$ is cyclic.

The result follows directly from this lemma because $(\Bbb Z/p\Bbb Z)^*$ is a field and a polynomial of degree $d$ over a field has at most $d$ roots. That is the arithmetic part of the result.

(*) This lemma appears verbatim in chapter X of André Weil's Number theory for beginners, which is a wonderful book.

  • $\begingroup$ Right, but this is not covered in my textbook and to prove this one would need some field theory, correct? I'm trying avoid polynomials and field theory. $\endgroup$ – farleyknight Nov 7 '18 at 17:55
  • $\begingroup$ @farleyknight, the lemma has a pure group theory proof. See for instance math.stackexchange.com/a/1615033/589. $\endgroup$ – lhf Nov 7 '18 at 17:56
  • $\begingroup$ Yes, but in your proof you use part of the hypothesis of the OP on that question. In other words, the part that says: "and so the hypothesis on A implies that ψ(d)=ϕ(d)." I don't have that assumption. $\endgroup$ – farleyknight Nov 7 '18 at 18:01
  • $\begingroup$ Specifically you rely on the fact that $\psi(d) ≤ \phi(d)$ for $U(p)$. $\endgroup$ – farleyknight Nov 7 '18 at 18:02

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.