2
$\begingroup$

Hi I would like a hint with the following congruence question. $1+x^{1}+x^{2}+\cdots +x^{6}\equiv 0\mod{29}$

Is there a formula I should be looking for to group the left hand side?

  • 3
    It might help to multiply by $x-1$, as long as you later throw out the additional nonsolution $x\equiv 1$.2012-02-03

2 Answers 2

4

Yep! Use the geometric series formula.

$\large 1+x+x^2+...+x^n = \frac{x^{n+1}-1}{x-1}$

3

As mentioned by Lopsy and Jonas Meyer, the solutions are all the solutions of $x^7\equiv 1 \pmod{29}$ except $x\equiv 1 \pmod{29}$.

For any $x$ relatively prime to $29$, $x^{28}\equiv 1 \pmod{29}$. So $(x^4)^7\equiv 1 \pmod{29}$. Conversely, if $y^7\equiv 1 \pmod{29}$, then $y\equiv x^4 \pmod{29}$ for some $x$. The simplest conceptual proof of this involves primitive roots, so we omit it.

Thus we want to find the fourth powers modulo $29$. Not much fun, except that we can confine the search to $14$ and below, since for example $(17)^4\equiv (-12)^4 \pmod {29}$. It is more efficient to first find the squares modulo $29$, since as you square the numbers $1$ to $14$, you will find that they fall in $\pm$ pairs, and therefore you will find $7$ solutions, one of which ($1$) is spurious.