0

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)

Student
  • 9,196
  • 8
  • 35
  • 81
  • 1
    "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... – DonAntonio Dec 04 '16 at 09:41
  • $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. – Claudius Dec 04 '16 at 10:48

1 Answers1

1

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.

Stefan4024
  • 35,843