Twin Primes Problem

Prove that when you multiply a pair of twin primes you get a number that has remainder 8 after division by 9. With one exception.

I'm already getting some good solutions. It's interesting to see people do it in slightly different ways.

I'll kill some space here just in case people can see the beginning of the description if it gets reposted.

OK, I think the most succinct answers go along these lines:

Twin primes must be of the form 3n-1 and 3n+1. Multiplying these two primes gives us 9n^2 - 1 = 9(n^2 - 1) + 8. So we have a remainder of 8 after division by 9. The exception is 3 and 5.

I've summarised answers there, but Alienturnedhuman was the first commenter who said something like that.

Some people used the same argument using 6n-1 and 6n+1. It is true that all primes larger than 3 are of this form. That works as well, but it's not quite as neat as above.

Some people used modular arithmetic. I can't assume all viewers know modular arithmetic, but one argument is:
All primes are 1, 2, 4, 5, 7, 8 mod 9 The possible pairs are
2x4 = 8 mod 9
5x7 = 35 = 8 mod 9
8x1 = 8 mod 9.

That's actually how I did it when given the problem. It's not the neatest solution.

[MrLordCoder]

The two prime numbers can be written as n+1 and n-1. Since one of the consecutive numbers n-1, n, n+1 is divisible by 3 and n-1 and n+1 are prime (so not divisible by 3 (Exception here)) so n is divisible by 3. So n*n is divisible by 9. Now: (n-1)*(n+1)=n*n-1.= -1 mod 9 = 8 mod 9.

[SteveZwartshortking]

Further proof, James Grime is out-standing in his field

[tone]

So, any non-3 prime can be written as either 1 mod 3 or 2 mod 3, since otherwise it'd be divisible by 3 and thus not a prime. Twin primes, because they differ by 2, must be opposites, so effectively we're multiplying 1 mod 3 and 2 mod 3, which gives us 2 mod 3 every time. But we need a result in mod 9, so let's look at the options there. 1 mod 3 is either 1, 4, or 7 mod 9, and 2 mod 3 is 2, 5, or 8. That leaves us with three twin possibilities: 2 and 4, 5 and 7, and 8 and 1. (or 8 and 10, if you need to see that they're two apart.) From there, we can just prove by exhaustion: 2*4=8, 8*1=8, and 5*7=35 which is 8 more than 27, a multiple of 9. So in all three possible twin combinations, we get a result of 8.

The exception, of course, is 3 and 5, because 3 is the only prime divisible by 3.

[AndrewKleinWW]

First sieve by only 2 and 3, this lays out all possible twin primes past 9, they are all separated by 6 and centered on a number with 3 as a prime factor. So multiplying any twin prime pair together gives a number 1 less than a number divisible by 9, so dividing by 9 leaves remainder 8. Exception is 3, 5, which obviously can't be sieved by 3.

[skrdman]

"See you later, calculator"

That's great. I'm going to try to remember that.

[matt]

That's easy.
Let the twin prime pair be (p, q) with p<q (so q=p+2). We can see that p must be in a form of 3k+2 for some integer k. (p can not be 3k, because it would be divisible by 3 and p also can not be 3k+1 because q would be 3k+1+2=3k+3 which is also divisible by 3.)
So p is 3k+2, therefore q=3k+4. If we multiply those together, we get (3k+2)(3k+4)=9k^2+18k+8, which is congruent to 8 mod 9. The only counterexample is (3, 5), where p is in a form of 3k but it's still a prime, that gives 6 as the remainder. QED.

[Ultras]

1. Three numbers in a row always contain a multiple of 3 and since it is neither of the twin primes then the number between them must be a multiple of 3.
2. So we can notate the twin primes as 3n-1 and 3n+1
3. Multiply them together and you get 9n² -1
4. This is one less than a multiple of 9 so it leaves a remainder of 8 when divided by 9

[adiptasen]

twin primes are in the form of (6n-1) and (6n+1)
so multiplying them we get
36n²-1 = 36(n²-1) +35
the first part is divisible by 9 and 35 got a remainder 8 when it is divided by 9
Exception occurs when the middle number b/w twin primes is not a multiple of 3 and the Product is less than 9 .

[j.vonhogen]

For every n, the square of 6n is divisible by 9. For every n, the product of 6n-1 and 6n+1 is 1 less than 6n^2. Twin primes are consecutive primes that differ by 2, which means they are of the form 6n-1 and 6n+1 (except for 3 and 5). Their product will therefore always have a remainder of 8 when divided by 9.

3 and 5 are the only twin primes of which the product doesn't have a remainder of 8 when divided by 9 (it has remainder 6).

[avananana]

I solved it the exact way you did, I'm not familiar with modular arthimetics but after spending about 20 minutes, I figured out the 3n-1 and 3n+1 formula, multiplied them together to get a new number p = 9(n^2 - 1) + 8, and p mod 9 will always equal to 8 since 9(n^2 - 1) is dividable by 9, and 8 is not. Very fun problem I have to say.

[trevorarashiro]

Every 3rd odd number is divisible by 3. For a twin primes couplet to exist, both must be in between multiples of three. One must be of the form 3k+2 and the other 3k+4. Multiplying them together, we get (27k^2+18k+8). The first two terms are multiples of 9 and, because of the +8, our number will always be 8 more than a multiple of 9.

[robinsparrow]

The product of to numbers adjacent to a central number is the square of the central minus 1. In order to get a product with 8 mod 9, this central number must be divisible by 3. If it weren't then one of the adjacent numbers must be. If this is the case, with one exception (when the number is exactly 3), one of the adjacent numbers would not be prime. Thus in order to have twin primes the number in the middle must be divisible by 3, thus the square of that number is divisible by 9, and thus the product of the twin primes on either side is one less than a multiple of 9.
This was really fun to work out, thanks!

[ZipplyZane]

I'm impressed by those who used a proof via modular arithmetic. It would have never occurred to me to do so. My brain instantly went to multiplying m-1 and m+1.

[matthewwrigley]

Modulo 9, primes can only be 1, 2, 4, 5, 7, or 8. If a number were 0, 3, or 6 (mod 9), then it would be divisible by 3, therefore not prime (discounting the prime p = 3).

Therefore, the only possible twin prime pairings, modulo 9, are:
(2, 4)
(5, 7)
(8, 1)

Hence the resulting products can only be:
2 x 4 = 8 (mod 9)
5 x 7 = 35 = 8 (mod 9)
8 x 1 = 8 (mod 9)

So in any case, if p and q are primes, with q = p + 2, then p x q = 8 (mod 9).

The only case where this can't work is where p = 3, and q = 5. Then we have 3 x 5 = 15 = 6 (mod 9).

[x.sanctus]

Square numbers have the possible remainders {0, 1, 4, 7} after division by 9. Since the product of two consecutive odd primes, that differ by two is of the form n^2 -1 their possible remainders are {8, 0, 3, 6}. Every case except a remainder of 8 implies, that at least one of these primes (again) must've been divisible by three; a contradiction unless the smaller one was the number three itself.

[joeyhardin]

because all primes except 2 and 3 are one more or less than a multiple of 6, a pair of twin primes will have one of each possibilities, so that the lower prime is 6n-1 for some integer n and the upper prime is 6n+1.
(6n-1)(6n+1) = 36n^2-1

when you factor 9 out of the first term, you get
9(4n^2)-1
which is one less than a multiple of 9. this also means that it is 8 more than a multiple of 9 (remainder 8 after division by 9) as you can see here when you rearrange a bit:
9(4(n-1)^2)+8

[dirfgiS]

Every prime apart from 2 and 3 can be written in the form 6k + 1 or 6k - 1 where k is a natural number. As we are working with twin primes, the twin primes p and q must take the form p = 6k -1 and q = 6k + 1, which makes them be two apart from each other. Multiplying p and q together gives pq = (6k - 1)(6k + 1) = 36k^2 -1 (they are conjugates). This expression is equal to a natural number multiple of 36, minus one. 36 is divisible by 9, but when you take away 1, it will leave a remainder of 8. QED. The exception to this is p = 3 and q = 5, as 3 cannot neither be expressed as 6k - 1 nor 6k + 1, and 2 does not have a twin prime, which makes 3 and 5 the only exception.

[natrijevkarbonat]

(3n+2)(3n+4)=9y+8 and n has to be a natural number. If n is a natural number then y is also a natural number but not necessarily the other way around. Did I solve it?

[snowfloofcathug]

You should mirror the video and put them beside each other, making Twin Grimes explaining Twin Primes :D

[Sirus]

Firstly: all twin prime pairs except 3, 5 can be written as (6n-1), (6n+1) for some integer n, due to the fact that all primes larger than 5 are of such form. If we evaluate the expression (6n-1)*(6n+1) mod 9 we get -1 mod 9 which is 8.
This concludes the proof.