Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.