2
$\begingroup$

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 :)

  • 0
    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?2012-09-14

1 Answers 1

2

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,$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.