# 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$ [closed]

The question is the natural generalization of the

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

## closed as off-topic by T. Bongers, kingW3, hardmath, Did, meselAug 12 '17 at 21:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – T. Bongers, kingW3, hardmath, Did, mesel
If this question can be reworded to fit the rules in the help center, please edit the question.

• Welcome to MSE! This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. – T. Bongers Aug 12 '17 at 19:40

## 1 Answer

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