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$

Question

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

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