Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would like to learn the following:

a) Prove that the equation $1 + x + x^2 = py$ has integer solutions for infinitely 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$.

share|cite|improve this question
nice question. but plz remove tag twins. – mick Jul 7 '13 at 0:07
up vote 3 down vote accepted

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$.

share|cite|improve this answer
Nicolas! Excellent analysis you have given. Thanks a lot. – vmrfdu123456 Nov 8 '12 at 9:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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