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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 12 '10 at 11:28
  • $\begingroup$ 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$. $\endgroup$ – yunone Sep 12 '10 at 11:55
  • 3
    $\begingroup$ 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. $\endgroup$ – Andrea Mori Sep 12 '10 at 12:55
  • $\begingroup$ 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. $\endgroup$ – 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,


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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