# Do there exist two primes $p<q$ such that $p^n-1\mid q^n-1$ for infinitely many $n$?

We can prove that there is no integer $n>1$ such that $2^n-1\mid 3^n-1$. This leads to the following question:

Is it true that for every pair of primes $p<q$ there are only finitely many integers $n$ such that $p^n-1\mid q^n-1$? Are there two primes $p<q$ and an integer $n>p+q$ such that $p^n-1\mid q^n-1$?Is it true that if $n>6$ then $2^n-1\nmid 5^n-1$?

Edit: Here are some examples: \begin{array}{ll} 2^{36}-1\mid 41^{36}-1, &3^{12}-1\mid 97^{12}-1,\\ 5^{6}-1\mid 37^{6}-1, &7^{4}-1\mid 151^{4}-1. \end{array}

Now I prove there is no integer $n>1$ such that $2^n-1\mid 3^n-1.$

Proof: Denote $A=2^n-1$ and $B=3^n-1$. If $n$ is even then $3$ divides $A$ but not $B$, a contradiction.

If $n$ is odd then $A\equiv -5\pmod {12}$. Since every prime greater than $3$ is $\equiv \pm1,\pm5 \pmod {12}$, some prime factor $p$ of $A$ must be congruent to $\pm5 \pmod {12}$. As $p \mid B$, we have $3^{n+1}\equiv 3 \pmod p$. Since $n+1$ is even, we get $(\frac{3}{p})=1$, a contradiction again.

• How do we prove $2^n-1$ can't divide $3^n-1$? What happens when you take the proof of that statement, and try to turn it into a proof for $p$ and $q$? – Gerry Myerson Jun 11 '13 at 12:16
• @Gerry Myerson Well,I'll add how to prove that statement and you can see that is not OK for $p$ and $q$. – Next Jun 11 '13 at 12:20
• @Samuel Like $k=m^2$, $\forall m \ge 2$, and $\forall n$? – awllower Jun 11 '13 at 12:35
• I think you meant to say that $A\equiv -5\pmod {12}$, when $n$ is odd, in the proof? Regards. – awllower Jun 11 '13 at 12:51
• @awllower Yes,thank you. – Next Jun 11 '13 at 12:58

Question : Is it true that for every pair of primes $p<q$ there are only finitely many integers $n$ such that $p^n-1\mid q^n-1$ ?

I will not provide a proof for this theorem here, but I will point to some references for the proof. Actually a generalization of your claim is true: for ever pair of integers $a<b$ there are only finitely many integers $n$ such that $a^n-1$ divides $b^n-1$ unless there $b=a^k$ for some integer $k$. In this document you will find the following claim proved (page 427):

Claim : If $(a^n-1)/(b^n-1)\in \mathbb Z$ for infinitely many $n\in \mathbb N$ then $b$ is a power of $a$.

The proof uses only some analysis and the Subspace theorem due to Wolfgang M. Schmidt (1972) which has many applications in number theory.

Remark although this gives an answer to your first question there may exist an elementary proof for this because the hypothesis $p,q$ are primes is very strong.

I have not thought about this particular problem yet, but let me prove somewhat related claim that if $x,y$ are integers and $x^n-1$ divides $y^n-1,$ $y>1$ for all $n\in\mathbb{N}$ (this condition can be eventually relaxed) then $y=x^m$ for some $m\in\mathbb{N}.$ This, in particular implies that both $x$ and $y$ cannot be primes simultaneously. The key is the following useful lemma.

Lemma. If $x_1....x_m\ge 1$ are distinct rational numbers and $\alpha_1,...\alpha_m\ne 0$ are real numbers such that $\lim_{n\to\infty}\sum_{k=1}^m\alpha_kx_k^n-m_n=0$ where $m_n\in\mathbb{N},$ then $x_i\in\mathbb{Z},$ for $1\le i\le m.$

Proof. Induction on $m.$ The base case is fairly interesting exercise, I will leave it for the reader. To prove a step of induction from $m$ to $m+1,$ we fix some $x_l=\frac{p}{q}.$ Observe, that $$\lim_{n\to\infty}\sum_{k=1}^mp\alpha_kx_k^n-pm_n=0$$ and $$\lim_{n\to\infty}\sum_{k=1}^mq\alpha_kx_k^{n+1}-qm_{n+1}=0.$$ Subtracting last two identities leads to $$\lim_{n\to\infty}\sum_{k=1}^m\alpha_kx_k^n(qx_k-p)-(qm_{n+1}-pm_n)=0.$$ Since $x_lq-p=0,$ we can apply induction hypothesis to conclude that $x_i\in\mathbb{N}$ for $i\ne l.$ We are left to note that $l$ was chosen arbitrary and thus, $x_i\in\mathbb{N}$ for $1\le m+1.$

Now, in order to apply this to our problem we pick such $m$ that $x^m\le y<x^{m+1}$ and take $m_i=\frac{y^i-1}{x^i-1},$ $x_i=\frac{y}{x^i},$ $\alpha_i=1$ for $1\le i\le m.$ Then $$m_n-\sum_{k=1}^m\alpha_kx_k^n=\frac{y^n-x^{mn}}{x^{mn}(x^n-1)}\to 0.$$ So all $x_i$ are integers. Thus, $$\frac{y^n-x^{mn}}{x^{mn}(x^n-1)}=0$$ for sufficiently large $n.$ Therefore $y=x^m.$

Note, that we can request $\lim_{n\to\infty}\sum_{k=1}^m\alpha_kx_k^n-m_n=0$ along some "fairly nice" subsequence $n_k.$ Thus, we do not require divisibility $x^n-1$ and $y^n-1$ for all $n.$

Remark 1. As to the second question, I do not think that there is something special about $n,$ in the sense that it can be fairly large. Good computer search should help to find a counterexample.

Remark 2. Starting from any prime $q$ and any $a>1,$ and $q^n-1$ divides $a^n-1$ we can take $x_m=a+m(q^{n}-1)$ and apply Dirichlet's theorem for arithmetic progressions to find infinitely many primes that satisfy our condition.