# Modulo equation : $\frac{n^{k+1}-1}{n-1} \equiv a{\pmod p}$

Can we have directly answer for this question :

$$\frac{n^{k+1}-1}{n-1} \equiv a{\pmod p}$$ (p is a prime and k,n is a fixed number)

My question is : with fixed number n, k and p, can we know value a ?

Thanks :)

-
Sure. Fermat's Theorem will greatly simplify things. – André Nicolas Sep 13 '12 at 15:59
Can you tell me, more, please. – hqt Sep 13 '12 at 16:24
Sorry, kind of busy. Someone will probably soon give an answer. If not, I will get to it (quite a bit) later. – André Nicolas Sep 13 '12 at 16:30
I don't understand the question. With fixed $n,k,p$, you can calculate $(n^{k+1}-1)/(n-1)$, reduce it modulo $p$, and there's your $a$. What do you really want? – Gerry Myerson Sep 14 '12 at 6:33

Let's us assume $n≠1$,else the L.H.S. will be undefined, also assume $n$ is any integer and integer $k≥-1$.

$(1)$If $k=-1,a\equiv 0{\pmod p}$ .

$(2)$If $k=0,a\equiv 1{\pmod p}$ .

$(3)$If $k>0$,

$(A)$If $p\mid (n-1)$ i.e., $n=1+ap$ for some integer $a$

Then, $n^{k+1}-1=(1+ap)^{k+1}-1=(k+1)ap+^{k+1}C_2(ap)^2+...$

So, $\frac{n^{k+1}-1}{n-1}$ $$=\frac{(k+1)ap+^{k+1}C_2(ap)^2+...}{ap}\equiv k+1 \pmod p \implies a \equiv k+1 \pmod p$$

$(B)$If $p∤(n-1)$ i.e., $(n-1,p)=1$,

(i)If $p\mid n,$ $$\frac{n^{k+1}-1}{n-1} \equiv 1 \pmod p\implies a \equiv 1 \pmod p$$

(ii)else $(p,n)=1$, let $ord_pn=d$ which is clearly $>1$.

If $k+1=q\cdot d+ r$ where $0≤r<d$,$n^{k+1}\equiv n^r \pmod p$

$$\implies n^{k+1}-1\equiv n^r-1 \pmod p$$

$$\implies \frac{n^{k+1}-1}{n-1}\equiv \frac{n^{r}-1}{n-1}\pmod p$$ as $(n-1,p)=1$

$$\implies a \equiv \frac{n^{r}-1}{n-1} \pmod p$$

$\equiv 0$ if $r=0$,

$\equiv(n^{r-1}+...+n+1)$ otherwise.

If $n\equiv m$ where $m$ can be in $(1,p-1)$ or in $(-\frac{p}{2}, \frac{p}{2})$, $n^t$ (where $t$ is any natural number) can be replaced with $m^t$ for the ease of calculation.

-