Divisibility of sum of exponents

188 Views Asked by At

Consider the sequence

$$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$

such that:

$$ ra^{n+1} \equiv r \mod M$$

and $a \ne 1$ and $a,r$ are both coprime to $M$

Is it always true then that:

$$ r + ra + \ ra^2 + \ ra^3 ... + \ ra^n \equiv 0 \mod M$$

Consider the case of $M = 7$ just to get a better feel for the problem:

For $ r = 2 \ a = 3 $

$$ 2 + 2*3 + 2*3^2 ... 2*3^5 = 2 \frac{1 - 3^6}{1 -3} \equiv 0 \mod 7 $$

We can also look at

$r = 2 \ a = 4 $

$$ 2 + 2*2 + 2*4 \equiv 2 + 4 + 1 \equiv 0 \mod 7 $$

Why does this appear to be the case? Is there counter-example

1

There are 1 best solutions below

5
On

Your example of $M = 7$ does not make sense unless you mean $ra^{n+1} \equiv r$. Then, since $\gcd(M,r) = 1$, we have $a^{n+1} \equiv 1 \pmod M$. You also probably mean $a$ is not $\equiv 1$.

Since $a$ is not $\equiv 1$, the sum is equal to $r \cdot \frac{a^{n+1}-1}{a-1} \equiv 0 \pmod M$.