2
$\begingroup$

Suppose $p$ is prime, $q|(p-1)$. Prove the congruence $1+x+\cdots+x^{q-1}\equiv 0 \pmod{p}$ has exactly $q$ solutions.

I have this as a homework assignment and I've having trouble proving it. I'm trying to use Lagrange's theorem:

If $p$ is prime, an $n$th degree polynomial has at most $n$ solutions mod $p$.

My attempt so far:

$q|(p-1)$ implies $p-1 = qr$ for some $r$ in $\mathbb{N}$

$1+x+\cdots+x^{p-1} = (1+x+\cdots+x^{q-1}) h(x)$ where $h(x)$ is a polynomial of degree $q(r-1)-1$

(since $x^{q(r-1)-1}x^{q-1}=x^{qr-q-1+q-1}=x^{qr-2}=x^{p-1}$)

but here I'm stuck. I'm not quite sure where to go from here. I think I can say that all the solutions of $1+x+\cdots+x^{p-1} \mod p$ are either solutions of $1+x+\cdots+x^{q-1}$ or $h(x)$ modilo $p$, but I'm not quite sure if that's true, or if it is, where to go from there. I'd appreciate any help or hints, thanks!

  • 0
    then use Fermat's little theorem together with Lagrange's theorem.2010-10-23

2 Answers 2

3

I'm assuming that when you say "congruence", you mean that you want to show that the congruence $x^{q-1} + \cdots + 1 \equiv 0 \pmod{p}$ has exactly $q$ solutions.

You are incorrect in saying that $1+x+\cdots + x^{p-1}$ is a multiple of $1+x+\cdots+x^{q-1}$. For example, if $p=7$ and $q=3$ (which divides $7-1=6$), you would need $1+x+x^2$ to divide $1+x+x^2+x^3+x^4+x^5+x^6$. But doing long division, you get $x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 = (x^2+x+1)(x^4+x) + 1,$ so there is a remainder. Your assertion is false, which is probably why you are stuck.

(The reason I knew you were incorrect in the assertion is: notice that $x^q-1 = (x^{q-1}+\cdots+1)(x-1)$ and $x^p-1 = (x^{p-1}+\cdots+1)(x-1)$. The only solution modulo $p$ to $x^{p}-1$ is $x=1$, because by Fermat's Little Theorem you have $x^p \equiv x \pmod{p}$ for all $x$; if $x^{q-1}+\cdots+1$ divides $x^{p-1}+\cdots + 1$, then $(x^{q-1}+\cdots+1)(x-1)$ divides $(x^{p-1}+\cdots+1)(x-1)$; so every root of $x^{q-1}+\cdots+1$ has to be a root of $x^p-1$. But $x^{q-1}+\cdots+1$ has a lot of roots, and that contradicts the fact that $x^p-1$ only has one).

As Qiaochu suggests, consider the polynomial $x^q - 1 = (x-1)(x^{q-1}+\cdots+1)$. Since $p$ is prime, $x^q-1\equiv 0\pmod{p}$ if and only if at least one of $x-1$ and $x^{q-1}+\cdots+1$ are congruent to $0$ modulo $p$; and since $q|p-1$, then $1^{q-1}+1^{q-2}+\cdots+1 = q\not\equiv 0 \pmod{p}$. So $a$ is a solution to the original congruence if and only if $a$ is a solution to $x^q-1 \equiv 0 \pmod{p}$ and $a\not\equiv 1 \pmod{p}$.

Now look at the multiplicative group modulo $p$, which has order $p-1$, and look at a primitive root modulo $p$.

If you do not know about primitive roots, you can still more or less push through your attempt if you are a little more careful. Instead of claiming that $x^{q-1}+\cdots+1$ divides $x^{p-1}+\cdots + 1$ (which is false), try to see if it divides $x^{p-1}-1$. By Fermat's Little Theorem, you know exactly how many roots modulo $p$ $x^{p-1}-1$ has. If you can find the $h(x)$ such that $(x^{q-1}+\cdots+1)h(x) = x^{p-1}-1$, then you know that every root of $x^{p-1}-1$ is either a root of $h(x)$ or a root of the polynomial you want. Then show that the two polynomials have no root in common, and use Lagrange's Theorem as you want to give an upper bound for the number of roots of $h(x)$, and hence a lower bound to the number of roots of $x^{q-1}+\cdots+x+1$. Then use Lagrange's Theorem again to get an upper bound.

  • 0
    @arturo: Even i was joking! I completely agree with you2010-10-23
2

$\rm\ q\:|\:p-1\ \Rightarrow\ x^q - 1\ $ divides the prime product $\rm\ x^{p-1} - 1\ =\ (x-1)\:(x-2)\:\cdots\:(x-p+1)\:.\ $ By uniqueness $\rm\ x^q-1\ $ is uniquely a product of $\rm\:q\:$ of the $\rm\:x-a_i\:,\:$ so it has precisely $\rm\:q\:$ roots.

REMARK $\ $ Products of primes factor uniquely over any integral domain, i.e. any other factorization into irreducibles is the same up to order and unit factors. Such uniqueness of prime factorizations is the trivial part of being a UFD. The nontrivial part is the existence of prime factorizations for all nonzero nonunits.