# Bijection between twin primes and numbers $n$ such that $n^2-1$ has exactly four positive divisors

I'm working my way through Niven's Introduction to Number Theory, and the wording of the following problem is making me unsure of my answer:

Show that there is a one-to-one correspondence between twin primes and numbers $n$ such that $n^2-1$ has just four positive divisors.

I felt an obvious bijection would be $f\colon A\rightarrow B\colon (p,p+2)\mapsto p+1$, where $A$ is the set of all pairs of twin primes, and $B$ is the set of all positive $n$ such that $n^2-1$ has only four positive divisors. $f$ is injective, and for any such $n$, if $n^2-1=(n-1)(n+1)$, has only four positive divisors, they must be $1,(n-1),(n+1),n^2-1$, implying that $n-1$ and $n+1$ are twin primes, and thus $(n-1,n+1)$ would be a suitable preimage.

However, I assumed the wording of the problem meant I should show a bijection from unordered pairs of twin primes to positive integers, but I'm not sure if the problem intended for me to find a bijection that takes a single prime that happens to be a twin prime, to any such $n$, not necessarily positive which is problematic since both $n$ and $-n$ give the same $n^2-1$. Have I interpreted this problem correctly? If not, do other bijections exist with the differing domains and ranges I mentioned above?

-
If n^2-1 = (n-1)(n+1) has exactly four divisors then n-1,n+1 are twin primes. This is the obvious correspondence and seems to be the problem's intention. –  Yuval Filmus Sep 12 '10 at 11:28
The thing that makes me skeptical is suppose $n=-4$. Then $n^2-1=15$, which has exactly 4 positive divisors 1,3,5,15. But $n-1=-5$ and $n+1=-3$, neither of which is prime, and so the bijection I wrote above wouldn't apply. I know it seems dumb, it's just that the problem didn't specify that the bijection be into only positive $n$. –  yunone Sep 12 '10 at 11:55
Well, the fact that prime numbers are positive is very conventional. In fact -3 satisfies the definition of prime element in the ring of integers: if -3 divides a product ab, then -3 divides either a or b. The minus sign is rather irrelevant since -1 is a unit (i.e. invertible). It seems to me that Niven's exercise could be best rephrased in terms of ideals. Note that p and -p generate the same ideal in Z. –  Andrea Mori Sep 12 '10 at 12:55
The goal of the problem might have been transforming a condition about pairs (twin primes) to a condition about single numbers (having exactly four factors), so that you could count the pairs using the singles, or for whatever other reason. There's nothing deeper here, even if there's a variant of the solution where all the numbers are signed (that's different only in outside appearance). I'm sure Niven has harder questions you're better off spending your time on. –  Yuval Filmus Sep 12 '10 at 17:29

As Yuval points out, (F(n-1=p, n+1=q) := n)^2-1 = pq is the obvious interpretation. If you want to interpret the problem as specifying as a domain for the bijection a single prime p for which either p+2 or p-2 is also prime, or two primes which are part of the same twin pair but given in either order, or if n is allowed to be negative while p and q are conventionally positive, then (in any of those cases) a bijection exists if and only if twin primes are infinite in number.

If you extend both the domain and range in this way then it still works: F(-n+1=p, -n-1=q) := n. Also if you extend the range and extend the domain by allowing negative primes then it still works without adding to the definition of F.

-

I did this same problem for a class on number theory, the book omits a constraint that n>3 since 3^2 -1 = 8 which is divisible by 1,2,4,8 and 4 is not prime it does however hold for all n>3. Intuitively this is a consequence of the fact that 2 is the only even prime and that the product of three consecutive integers is divisible by 6 (n-1 being divisible by two would typically eliminate its candidacy for being prime EXCEPT for the n-1 = 2 case). Proving that a one-to-one correspondence exists is done by proving a that there is an iff statement relating (n-1),(n+1) being prime and (n-1)(n+1) having 4 dividers. Since this would imply that the set of all n such that n^2-1 has 4 dividers is equal to the set of n s.t. (n-1),(n+1) are prime and the function mapping a set back to itself is a trivial bijective map.

One direction is pretty easy, (n-1),(n+1) prime => s = (n-1)(n+1) = p1*p2 therefore s has 4 dividers, 1,s,p1, and p2.

The other direction is left for you to figure out,

-