# An interesting problem which only needs elementary number theory

## A problem about elementary number theory

While writing my paper, I came across the following problem: (all the discussion assume that $q$ is prime and $\alpha$ is a positive integer. ) We first ask :given an integer $\alpha$, can we always find a prime $q$ such that $q-\alpha$ divides $\alpha^{2}-\alpha$? For this , I have already known that: for certain form of $\alpha$, no such $q$ can be found. Actually we have the following

Proposition 1: If $\alpha =2p+1$, and $p$ is prime such that $p \equiv 11 \;\text{or} \; 41 \pmod {60}$ , then no prime $q$ satisfy $q-\alpha$ divides $\alpha^{2}-\alpha$.

Proof of Prop1:

Let $\alpha=2p+1$, $p$ is a prime and $p \equiv 11 \;\text{or} \; 41 \pmod {60}$, we next prove by contradiction that there doesn't exits prime $q$, such that $q-\alpha$ divides $\alpha^{2}-\alpha$.

Note that $q=2$ is impossible , since $2-\alpha | \alpha^{2}-\alpha$ imply $\alpha=0,1,3,or \;4$ all contradicts our assumption. We next assume that $q$ is an odd prime. Since $q |\alpha \; \text{or} \; q\nmid \alpha$,we have two cases:

Case 1 :$q\nmid \alpha$

In this case $gcd(q-\alpha,\alpha)=gcd(q,\alpha)=1$. So $q-\alpha$ divides $\alpha^{2}-\alpha=\alpha(\alpha-1)$ imply $q-\alpha |\alpha-1=2p$.Thus $q=(2p+1)\pm1,(2p+1)\pm2,(2p+1)\pm p,(2p+1)\pm 2p$. However when $p \equiv 11 \;\text{or} \; 41 \pmod {60}$,all the above form of $q$ can't be prime.

Case 2$:q|\alpha$

Suppose $\alpha=rq$. Since $q-\alpha|\alpha^{2}-\alpha$, we have $q-\alpha|\alpha^{2}-\alpha=\alpha^2-q^2+q-\alpha+q^2-q$. So $q-\alpha|q^2-q$,namely $q-rq|q^2-q$,which imply $r-1|q-1$. But $\alpha=2p+1=rq=r(q-1)+r$, so $2p=r(q-1)+r-1$ .Thus we get $r-1|2p$, so $r=2,3,p+1,2p+1$. Note that $\alpha=2p+1 =rq$ is odd ,so $r$ must also be odd. Only $r=3,2p+1$ are possible . If $r=2p+1$,then $r=2p+1=\alpha=rq$, which is impossible since $q$ is a prime. If $r=3$, then $2p+1=3q\equiv 0\pmod 3$, which imply $p\equiv 1\pmod 3$.This contradicts with $p \equiv 11 \;\text{or} \; 41 \pmod {60}$.

My question is what can we say if we replace $\alpha^2-\alpha$ by $\alpha^3-\alpha$ , or more generally by $\alpha^l-\alpha$ ( $l\geq 3$ is an integer). Given an integer $\alpha$, can we always find a prime $q$ such that $q-\alpha |\alpha^3-\alpha$ . I wrote a computer program to test all $\alpha\leq2000$ and found that for every $1\leq\alpha<1291$ we can find a prime $q$ such that $q-\alpha|\alpha^3-\alpha$, $1291$ is the first $\alpha$ that we can't find $q$ satisfying $q-\alpha|\alpha^3-\alpha$. When we enlarge the scope of $\alpha$, we can find more $\alpha$ for which no prime $q$ can be found.

Instinctively, I feel that for any $l\geq 2$ there exists infinity many $\alpha$ such that we can't find prime $q$ which makes $q-\alpha |\alpha^l-\alpha$. To prove that I think we need to provide a certain form of $\alpha$ (just like the above case $\alpha =2p+1,p \equiv 11 \;\text{or} \; 41 \pmod {60}$ for $\alpha^2-\alpha$), I did my best but I still don't know how to construct the form. If my intuition is wrong,how to prove that there are only finitely many such $\alpha$.If you are good at such problem, please do have a try. I desperately need your help, thank you !

• Thanks for your effort but if we let $q=\alpha-1$ we will find it is not feasible – 王李远 Sep 8 '16 at 1:08
• I think you don't need to delete it. Although unfeasible, to think of Mersenne Prime is really an encouraging idea. – 王李远 Sep 8 '16 at 7:08
• Now posted to MO, mathoverflow.net/questions/249829/… – Gerry Myerson Sep 14 '16 at 5:20