8
$\begingroup$

Let $x$ be a unit in $\mathbb Z/ n \mathbb Z$ of multiplicative order $m$. I am trying to determine when it is that $$ \sum_{i=0}^{m-1} x^i \equiv 0 \mod n . $$ Is this kind of situation something that has been studied? If so, I would be very interested in any suggestions of books that discuss this kind of problem.

  • 0
    As this is (algebraically) just $(x^m-1)/(x-1)$, as long as $x\neq 1$ it's equivalent to $x^m\equiv 1\pmod n$, which means it should always be true under the conditions you propose. Can you show a counterexample?2012-06-29
  • 1
    I'm concerned about the possibility that $\gcd(x-1,n) \neq 1$. This seems like it can cause problems.2012-06-29
  • 1
    As an simple example of where it doesn't work, there is $x=5$ and $n=12$.2012-06-29
  • 1
    Or for that matter, $x=3$ and $n=8$. Then the sum is $1$.2012-06-29
  • 0
    Oh, of course - I missed that there might be zero divisors in the ring. :/ Mea culpa!2012-06-29
  • 0
    @Arturo, if $x=3$ and $n=8$ then $m=2$ and the sum is $1+3=4$.2012-06-29
  • 0
    @Gerry: Right; I got distracted by the $m-1$. In any case, the sum does not add up to $0$ modulo $8$.2012-06-29
  • 0
    It's equivalent to $(x-1,n)^2\mid(x^m-1)$.2012-06-29
  • 0
    @anon How do you see that?2012-06-29
  • 0
    Nevermind, it's necessary but not sufficient: $$n\mid \frac{x^m-1}{x-1}$$ $$\iff n\mid \frac{x^m-1}{(x-1,n)}$$ $$\iff n(x-1,n)\mid (x^m-1)$$ $$\implies (x-1,n)^2\mid (x^m-1).$$ I incorrectly applied CRT to the 2nd-to-last line.2012-06-29

1 Answers 1

3

(Below I treat $x$ as an integer whose reduction $\bmod n$ is a unit of order $m$. This allows me to treat $\frac{x^m - 1}{x - 1}$ as an integer and consider its reduction $\bmod n$ without dividing by a zero divisor.)

As usual, the Chinese Remainder Theorem is your friend. We can reduce to the case that $n$ is a prime power $p^k$. If $p \nmid x-1$, then the geometric series argument works and the sum is just $0 \bmod p^k$.

If $p | x-1$, the situation gets a little more complicated. We will need to introduce the following fundamental notion: for an integer $n$, the $p$-adic valuation $\nu_p(n)$ is the greatest $k$ such that $p^k | n$.

Theorem (lifting the exponent): Let $p$ be an odd prime and let $x, y$ be integers relatively prime to $p$ such that $p | x-y$. Then $$\nu_p(x^n - y^n) = \nu_p(x - y) + \nu_p(n).$$

Proof. Induction. See these notes.

Applying the above it follows that for odd $p$, if $p | x-1$ then $$\nu_p \left( \frac{x^m - 1}{x - 1} \right) = \nu_p(m).$$

Thus $\frac{x^m - 1}{x - 1} \equiv 0 \bmod p^k$ if and only if $p^k | m$. Hence:

If $n$ is odd then $\frac{x^m - 1}{x - 1} \equiv 0 \bmod n$ if and only if for every prime factor $p$ of $n$, either $p \nmid x-1$ or $p^k | m$.

Okay, so what if $p = 2$? In the above notes you will also find the following result.

Theorem (lifting the exponent at $2$): Let $x, y$ be odd integers such that $4 | x-y$. Then $$\nu_2(x^n - y^n) = \nu_2(x - y) + \nu_2(n).$$

So if $4 | x-1$ then the conclusion is the same as above. Otherwise, write $$x = 1 + 2y$$

where $y$ is odd. If $m$ is odd, then $$x^m = 1 + 2my + ...$$

where the remaining terms are divisible by $4$, and we conclude that $\nu_2(x^m - 1) = 2$, hence $\nu_2 \left( \frac{x^m - 1}{x - 1} \right) = 0$, so the sum is not divisible by $2^k$. If $m = 2 \ell$ is even, then $4 | x^2 - 1$, hence $$\nu_2(x^{2\ell} - 1) = \nu_2(x^2 - 1) + \nu_2(\ell) = \nu_2(x + 1) + \nu_2(m).$$

This gives $$\nu_2 \left( \frac{x^m - 1}{x - 1} \right) = \nu_2(y + 1) + \nu_2(m).$$

Thus $\frac{x^m - 1}{x - 1} \equiv 0 \bmod 2^k$ if and only if $2^k | m(y+1)$, and this can occur. So if $n$ is not odd then the above argument still applies to all the odd prime factors of $n$ and we conclude that

if $n = 2^k o, k \ge 1$ where $o$ is odd, then $\frac{x^m - 1}{x - 1} \equiv 0 \bmod n$ if and only if $\frac{x^m - 1}{x - 1} \equiv 0 \bmod o$ and either $x \equiv 1 \bmod 4$ and $2^k | m$ or $x \equiv 3 \bmod 4$ and $2^k | m \left( \frac{x+1}{2} \right)$.