# 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$?

#### Solutions Collecting From Web of "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$"

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