# some problems related to primes

I would like to learn the following:

a) Prove that the equation $1 + x + x^2 = py$ has integer solutions for inﬁnitely many primes $p$.

b) Twin primes are those difference by 2. Show that 5 is the only prime belonging to two such pairs. Show also that there is a one-to-one correspondence between twin primes and positive integers n such that $d(n^2-1) = 4$, where as above $d(k)$ stands for the number of divisors of $k$.

• nice question. but plz remove tag twins. – mick Jul 7 '13 at 0:07

a) The proof is a modification of the "Euclid" proof that there are infinitely many primes. Let $p_1=3$. Putting $x=1$ and $y=1$, we see that $1+x+x^2=py$ has a solution.

Now suppose that we have found $n$ primes $p_1,p_2,\dots,p_n$ such that $1+x+x^2=p_iy$ has a solution for any $i$ from $1$ to $n$. We exhibit a new prime $p_{n+1}$ such that $1+x+x^2=p_{n+1}y$ has a solution.

Consider the number $1+(p_1p_2\cdots p_n)+(p_1p_2\cdots p_n)^2$. This is an integer $\gt 1$, so has a prime divisor $p_{n+1}$. Any such $p_{n+1}$ must be distinct from $p_1,p_2,\dots,p_n$. This is because if $p_{n+1}=p_i$, where $1\le i\le n$, then $p_i$ divides $(p_1p_2\cdots p_n)+(p_1p_2\cdots p_n)^2$, so cannot divide $1+ (p_1p_2\cdots p_n)+(p_1p_2\cdots p_n)^2$.

Thus we have found a new prime $p_{n+1}$ such that $1+x+x^2=p_{n+1}y$ has a solution.

b) The number $5$ belongs to the pairs $(3,5)$ and $(5,7)$. It is clear that $2$ does not belong to any pair, and $3$ belongs to only $1$ pair. We show that any prime $p\ge 7$ cannot belong to more than one pair. Suppose to the contrary that $p$ does. Then $p-2$, $p$, and $p+2$ are prime. Note that if $x$ is any integer, then one of $x-2$, $x$, or $x+2$ is divisible by $3$. A number divisible by $3$ and greater than $3$ cannot be prime.

For the second part of the question, we ask when $d(n^2-1)=4$. If $n$ is even, then $n-1$ and $n+1$ are relatively prime, so $d((n-1)(n+1))=d(n-1)d(n+1)$. But $1$ is the only $k$ such that $d(k)=1$. So we must have $d(n-1)=d(n+1)=2$. That forces the pair $(n-1,n+1)$ to be a pair of twin primes.

Now examine the case $n$ odd. Then $(n-1)(n+1)$ is divisible by $8$, so has the divisors $1$, $2$, $4$ and $8$. Since $d(n^2-1)=4$, it can have no others. Thus $n^2-1=8$, giving $n=3$.

So the set $A$ of numbers $n-1$ such that $d(n^2-1)=4$ consist of $2$ plus the smaller primes in a twin prime pair. This set can be easily put in one to one correspondence with the set $B$ of smaller primes in twin prime pairs. Just list the two sets as $a_1,a_2,\dots$ and $b_1,b_2,\dots$ and map $a_i$ to $b_i$.

But the one-to-one correspondence bit has absolutely nothing to do with twin primes. For any two infinite sets of natural numbers can be put in one to one correspondence. So to prove there is a one to one correspondence, we need not have done any analysis of the $n$ such that $d(n^2-1)=4$.

• Nicolas! Excellent analysis you have given. Thanks a lot. – vmrfdu123456 Nov 8 '12 at 9:17
• Regarding your last paragraph... You are relying on the Twin Prime Conjecture, which is not known. We still need the analysis on n because it is not known whether either of these sets are finite or infinite. – Tony Mottaz Sep 26 '16 at 19:32