0
$\begingroup$

Lagrange's Theorem: If $p$ is a prime and $$f(x)=a_nx^n+a_{n-1}^{n-1}+....+a_0, \text{ where }a_n\not\equiv 0\pmod p.$$ is a polynomial of degree $n\geq 1$ with integral coefficients, then the congruence $$f(x)\equiv 0\pmod p$$ has at most $n$ incongruent solutions.

Corollary: If $p$ is a prime and $d|p-1$, then the congruence $$x^d-1\equiv 0\pmod p$$ has exatcly $d$ solutions.

I am facing some difficulty in understanding the proof outlined in the book Elementary Number Theory by David M. Burton.

Since $d|p-1$ we have $x^{p-1}-1=(x^d-1)f(x)$, where the degree of $f(x)$ is $p-1-d.$ We know that $x^{p-1}-1\equiv 0\pmod p$ has exactly $p-1$ incongruent solutions modulo $p$, the solutions being $1,2,3,...,p-1.$ Now any solution $x=a$ of $x^{p-1}-1\equiv 0\pmod p$ which is not a solution of $f(x)$ must be a solution of $x^d-1\equiv 0\pmod p.$ Since $f(x)\equiv 0\pmod p$ has atmost $p-1-d$ (Due to Lagrange's Theorem) and $x^{p-1}-1\equiv 0\pmod p$ has $p-1$ solutions, this implies that the equation $x^d-1\equiv 0\pmod p$ has at least $$p-1-(p-1-d)=d$$ solutions and since the maximum possible number of solutions is $d$ (Lagrange's Theorem) we conclude that $x^d-1\equiv 0\pmod p$ has exactly $d$ solutions.

I don't understand the part in bold. Please explain. (Using elementary knowledge of Number Theory)

$\endgroup$
  • 1
    $\begingroup$ "Lagrange's theorem"? Never heard of this name for this theorem, but what it says follows at once from what we know about fields: over a field, any field, a polynomial equation $\;f(x)=0\;$ has at most $\;\deg f\;$ different solutions (or different roots of the polynomial $\;f\;$ ), and they even use this in the proof you post, as how otherwise can be justified their claim that $\;x^{p-1}=0\pmod p\;$ has $\;p-1\;$ solutions? Unless they're working all this without any field theory and using Fermat's Little Theorem and etc... $\endgroup$ – DonAntonio Dec 4 '16 at 9:41
  • $\begingroup$ $f(x)$ is actually a monic polynomial, so, in particular, its leading coefficient is $\not\equiv 0\mod p$ and hence Lagrange’s Theorem is applicable. $\endgroup$ – Claudius Dec 4 '16 at 10:48
0
$\begingroup$

The Lagrange Theorem you're talking about is different from the more known Langrange Theorem about Groups. This one says that a polynomial $f(x)$ either has all of it's coefficients divisible by prime $p$, or $f(x) \equiv 0 \pmod p$ has at most $\deg f$ incongruent solutions. You can read about this one here

Now back to your question. $x^{p-1} - 1$ has exactly $p-1$ zeros modulo $p$. Now from the Theorem $f(x)$ has at most $\deg f = p-1-d$ zeroes modulo $p$. But since $x^{p-1} - 1 = (x^d - 1)f(x)$ it means that $(x^d - 1)f(x)$ has exactly $p-1$ zero modulo $p$. But for a zero of this polynomial at least one of the factors must be zero. As $f(x) \equiv 0 \pmod p$ for at most $p-1-d$ zeroes of $x^{p-1} - 1$ it follows that $x^d - 1$ is equivalent to $0$ modulo $p$ for at least $p-1 - (p-1-d) = d$ zeroes.

$\endgroup$

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.