4
$\begingroup$
  • $p$ is a prime number.

  • $G$ is a group of integers $\{1,2,\dots,p-1\}$ under multiplication mod $p$.

  • $d$ is a divisor of $(p-1)$

Is it possible to prove that the number of elements $a$ in $G$ such that $a^d\equiv1$ (mod $p$) is exactly $d$?

The Fermat's little theorem $a^{p-1} \equiv1$ should come in handy somewhere.

$\endgroup$
  • $\begingroup$ Can one use the fact that there is a primitive root? $\endgroup$ – André Nicolas Oct 21 '14 at 21:45
  • $\begingroup$ @AndréNicolas In fact, this result is stronger... $\endgroup$ – ajotatxe Oct 21 '14 at 21:52
  • $\begingroup$ Yes, if course it's possible. It follows from the fact that $G$ is cyclic. $\endgroup$ – egreg Oct 21 '14 at 21:56
  • $\begingroup$ @egreg To say that $G$ is cyclic is the same as to say that $G$ has a primitive root. $\endgroup$ – ajotatxe Oct 21 '14 at 21:58
  • $\begingroup$ @ajotatxe Yes, of course, but perhaps it's clearer terminology for the OP. $\endgroup$ – egreg Oct 21 '14 at 22:04
4
$\begingroup$

Traditionally this result is used as a lemma in the process of proving that primes possess primitive roots, so it is possible to prove this result without invoking primitive roots.

Usually the proof relies on the following fact: let $p$ be a prime number, and let $f(x) = c_k x^k + \cdots + c_1 x + c_0$ be a polynomial with integer coefficients, where $p\nmid c_k$. Then $f(x)\equiv0\pmod p$ has at most $k$ solutions (meaning, at most $k$ residue classes modulo $p$ contain integers that are solutions to the congruence).

To derive the OP's result from this, note that if $d\mid(p-1)$, so that $p-1=de$, then $$ x^{p-1} - 1 = (x^d-1)(x^{(e-1)d} + \cdots + x^d + 1). $$ But the left-hand polynomial has exactly $p-1$ roots modulo $p$ by Fermat's little theorem, while the second polynomial on the right-hand side has at most $(e-1)d$ roots modulo $p$. Therefore $x^d-1$ must have at least $(p-1)-(e-1)d=d$ roots modulo $p$ (hence has exactly $d$ roots, since it has at most $d$).

$\endgroup$
  • $\begingroup$ Thank you Greg. Thank you very much for your response. For the last part, I got that $p−(e−1)d=d+1$ instead of $d$. Am I missing a 1 somewhere? $\endgroup$ – Alicia Hargrove Oct 22 '14 at 22:23
  • $\begingroup$ you're right - typo corrected :) $\endgroup$ – Greg Martin Oct 22 '14 at 22:24
  • $\begingroup$ Thanks Greg! Just one more question: for the polynomial $f(x)$, do we require that $p$ doesn't divide only $c_k$, or all $c_i$ ($1\le i \le k$)? $\endgroup$ – Alicia Hargrove Oct 22 '14 at 22:27
  • 1
    $\begingroup$ Just $c_k$. We need the polynomial to "have degree $k$ modulo $p$". For example, we shouldn't think of $10x^3+2x^2-5x-3\equiv0\pmod5$ as a cubic congruence - we should think of it as a quadratic congruence. $\endgroup$ – Greg Martin Oct 22 '14 at 22:34
  • 1
    $\begingroup$ Looking back at the question, I am still a little unsure about one part. Could you pleas elaborate a little more on how may one argue that $(x^{(e-1)d} + x^{(e-2)d} + \dots + x^d + 1)$ has at most $(e-1)d$ roots? $\endgroup$ – Alicia Hargrove Oct 23 '14 at 5:57

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.