Number Theory – Do Two Primes p

divisibilityelementary-number-theorynumber theory

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.

Best Answer

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.