3
$\begingroup$

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 !

REMARK Someone has point out that I was wrong in saying: $1291 $ is the first $\alpha $ that we can't find $q$ satisfying $q-\alpha|\alpha^3-\alpha $. Actually $\alpha=21362$ should be the first counter example! With this fact,it seems that the form of $\alpha$ can be more difficult to find than I previously imagined. However, I still don't think there are finitely such $\alpha$.

$\endgroup$
10
  • $\begingroup$ Which factor of $182^3 - 182$ is of the form $q-182$ with $q$ prime? $\endgroup$ Sep 14, 2016 at 3:58
  • $\begingroup$ just take q=179 $\endgroup$
    – 王李远
    Sep 14, 2016 at 4:18
  • $\begingroup$ Sorry, I was just looking at positive factors. $\endgroup$ Sep 14, 2016 at 4:30
  • 1
    $\begingroup$ OTOH $\alpha = 21362$ seems to be a genuine example. $\endgroup$ Sep 14, 2016 at 4:42
  • 1
    $\begingroup$ Previously posted to m.se, math.stackexchange.com/questions/1917847/… $\endgroup$ Sep 14, 2016 at 5:19

1 Answer 1

3
$\begingroup$

I am not sure about only using elementary number theory but here is an approach using the Bateman-Horn conjecture. Maybe one can get by with a bit less using sieve methods but I will leave that to the specialists.

Let $\alpha$ be of the form $210n+160$ where $n$ an integer and assume that $\alpha/10 = 21n+16, (\alpha -1)/3 = 70n+53$ and $(\alpha +1)/7 = 30n+23$ are all prime. The Bateman-Horn conjecture implies that this happens for infinitely many $n$ with the expected frequency. For this $\alpha$ to work we need that $\alpha + d$ and $\alpha - d$ are not prime for $d$ running through the $128$ positive divisors of $\alpha^3-\alpha$. (The primality conditions are to restrict the number of factors of $\alpha^3-\alpha$). Now, the frequency of the $n$'s for which one of these $256$ conditions fail is lower, again by Bateman-Horn (it's possible that the required upper bound can be proved unconditionally). So this gives the required examples.

The first few values of $\alpha$ obtained this way are $496390, 1169230, 1239790, 3806410, 4176430$.

$\endgroup$
1
  • $\begingroup$ It's really a great idea to think in that way, which I believe can be improved.Thanks a lot $\endgroup$
    – 王李远
    Sep 15, 2016 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.