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!

  • 2
    The roots of x^{q-1} + ... + 1 are the elements of order dividing q in the multiplicative group, except 1. The multiplicative group is cyclic of order p-1 because primitive roots exist, and q | p-1, so... (equivalently, use Fermat's little theorem.)2010-10-23
  • 0
    You did not write a congruence, you wrote a polynomial. Did you mean $1+x+\cdots+x^{q-1}\equiv 0 \pmod{p}$, perhaps?2010-10-23
  • 0
    @Qiaochu Yuan: thanks for the help but I think we're supposed to do this using pure number theory, without any group theory stuff.2010-10-23
  • 0
    @Arturo Magidin: yeah, i was being a bit loose with my notation. Also, didn't realize this website had TeX support.2010-10-23
  • 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
    Thanks so much for such a quick and in-depth answer. I really appreciate the help, that makes a lot of sense.2010-10-23
  • 0
    @Nate: Then you might want to (i) vote up the answer; and (ii) hold off on accepting a bit to see if you get better answers! (Not that I mind the boost...)2010-10-23
  • 0
    @Arturo: Nate can't vote as she has rep<152010-10-23
  • 0
    @Chandru: in any case, she should hold off accepting a bit. No doubt Bill Dubuque will come along in good order to give a slick, terse, solution. It's often a good idea to let a reply sit in a bit before accepting.2010-10-23
  • 0
    @Arturo Magidin: Well, you have lot of trust on Bill, don't you!2010-10-23
  • 0
    @Arturo: ah, sorry about that. Good to know for next time i ask a question.2010-10-23
  • 0
    @Chandru: It's not trust when it is based on long experience, just like it is not "faith" if it is based on evidence. And it was somewhat of a joke in any case. But I did mean it about waiting a bit before accepting solutions. Especially for a homework problem like this: Maybe I'll lead Nate into a blind alley! At the very least, he should see if my explanation actually leads to understanding and a solution before accepting it.2010-10-23
  • 0
    @Nate: See my response to Chandru. It's not a faux-pas to accept an answer quickly; but especially with a homework where you are given a push rather than an answer, you might want to wait and see if it actually pans out. (-:2010-10-23
  • 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.