Given a fixed prime number $p$ and fixed positive integers $a$ and $k$; Find all positive integers $n$ such that $p^k \mid a^n-1$ The question is the natural generalization of the 
Find all positive integers solutions such that $3^k$ divides $2^n-1$ .
Let $p$ to be a prime number and let $k$ & $a$ be fixed natural numbers. 
Find all natural numbers $n$, such that $p^k \mid a^n-1$?
 A: At first notice that if $\gcd(a,p) > 1$, then clearly there is no such natural number $n$. So we can assume that $\gcd(a,p) = 1$. 


Let $a$ be a natural number such that $\gcd(a,M)=1$. 
By the $\text{ord}_M(a)$ we mean the minimum power $r$ 
for which $a^r-1$ is divisible by $M$.  
Lemma(II): Let $a$ be a natural number such that $\gcd(a,M)=1$. 
Let $R$ to be an arbitrary natural number. 
Then we have:
$$ M \mid a^R-1  \ \ \ \Longleftrightarrow \ \ \ \text{ord}_M(a) \mid R \ \ \ . $$


By the $v_p(t)$, we mean the highest power of $p$ which divides $t$. 
Now see the Lemma1 from here: 
$p$-adic valuation of $x^n+1$[or how many times does a prime number divides $x^n+1$]
From the mentioned lemma1 and Lemma(II) we have the following lemma: 
Lemma(III): Let $p$ to be an odd prime and let $a$ be a natural number such that $\gcd(a,p)=1$. 
Let $r:=\text{ord}_p(a)$; i.e. 
the minimum power $r$ for which $a^r-1$ is divisible by $p$. 
Also let $t:=v_p(a^r-1)$; i.e. the highest power of $p$ which divides $a^r-1$. 
If $k \leq t$ let $s:=0$, else let $s:=k-t$. 
Then we have: 
$$\text{ord}_{p^k}(a)=rp^s.$$ 

Lemma(IV): Let $p=2$ 
and assume that $a\overset{4}{\equiv} 1$.
Then we have $1=\text{ord}_4(a)$. 
Also let $t:=v_2(a-1)$; i.e. the highest power of $2$ which divides $a-1$. 
If $k \leq t$ let $s:=0$, else let $s:=k-t$. 
Then we have: 
$$\text{ord}_{2^k}(a)=2^s.$$ 

Lemma(V): Let $p=2$ 
and assume that $a\overset{4}{\equiv} 3$.
Then we have $2=\text{ord}_4(a)$. 
Also let $t:=v_2(a^2-1)$; i.e. the highest power of $2$ which divides $a^2-1$. 
If $k=1$ let $s:=-1$, if $1 < k \leq t$ let $s:=0$, else let $s:=k-t$. 
Then we have: 
$$\text{ord}_{2^k}(a)=2.2^s \ .$$ 








*

*First case: Assume that $p$ be an odd prime.
then let $r:=\text{ord}_p(a)$; i.e. 
the minimum power $r$ for which $a^r-1$ is divisible by $p$. 
Also let $t:=v_p(a^r-1)$; i.e. the highest power of $p$ which divides $a^r-1$. 
If $k \leq t$ let $s:=0$, else let $s:=k-t$. 
Then Lemma(III) implies the following proposition : 


Proposition3: $n$ satisfies the above divisibility diophantine equation 
if and only if it is divisible by $rp^s$.




*

*Second case: Assume that $p=2$ 
and assume that $a\overset{4}{\equiv} 1$,
then we have $1=\text{ord}_4(a)$. 
Also let $t:=v_2(a-1)=v_2(a^1-1)$; 
i.e. the highest power of $2$ which divides $a-1$. 
If $k \leq t$ let $s:=0$, else let $s:=k-t$. 
Then Lemma(IV) implies the following proposition : 


Proposition4: $n$ satisfies the above divisibility diophantine equation 
if and only if it is divisible by $2^s$.
