This is the day 2 post of the challenge quiz week by 2IIM Online CAT Coaching :

Challenge Quiz Puzzle – Day 2:

Today’s task can be outlined in very simple fashion. Generate an Arithmetic Progression with 6 terms such that all six numbers are prime.

**Solution**

We want to find 6 prime numbers in Arithmetic Progression. This question is going to be all about finding some insight about the common difference.

Let us start with some simple inferences.

The common difference has to be an even number.

Why? Otherwise, we will have even and odd numbers in the sequence and they cannot be prime. This seems a bleeding obvious idea, but is going to be the starting step for us. So, let us revisit this.

So, if every term of an AP has to be odd, the common difference has to be an even number. If every term in an AP should not be a multiple of 2, then the common difference ** should** be a multiple of 2. If we take a number that is not a multiple of 2 and keep adding a multiple of 2 to it, we will never get a multiple of 2 in the sequence. Bleeding obvious stuff, but we are building something here.

Can we extrapolate this? If you have a number that is not a multiple of 3 and we keep adding multiples of 3, we will never get a multiple of 3. This also seems to be true. Might the converse be true? If we have a number that is not a multiple of 3, and we keep adding a non-multiple of 3, we will surely get to a multiple of 3 sooner or later. Is the above statement true? Can you verify this?

Let us take the first number, say, ‘a’ and common difference ‘d’. Neither a nor d are multiples of 3. If we consider a, a + d, a + 2d, a + 3d, a + 4d etc, we are suggesting that there has to be a multiple of 3 here. First let us verify this and then we can think about within which term will we definitely get a multiple of 3.

Let the terms a, a + d, a + 2d, a + 3d, a + 4d be T1, T2, T3, T4, T5 etc in this sequence. Let us make one simple inference here

Let us consider the first three terms. No two terms will leave the same remainder on division by 3. Because then the difference would be a multiple of 3. The difference between any two terms here would be either d or 2d. So, we can say that T1, T2, T3 will have to have different remainders on division by 3. So, one of them HAS to have the remainder 0 on division by 3. Or, one of the terms has to be a multiple of 3 and therefore not prime.

So, we CANNOT have three terms in AP such that all three are prime and the common difference is not a multiple of 3. {The only exception to this rule is 3,5, 7. Figure out why that exception exists}

From here on, it is very simple. Just by extrapolating, we can say that we cannot have 5 terms in an AP without the common difference being a multiple of 5 {Find the exception here as well}.

So, if we need to have six terms in AP, the common difference has to be a multiple of 2, 3 and 5. Or, it has to be a multiple of 30. So, we can have common difference as 30, 60 etc.

From here on, it is down to trial and error. Pick up prime number – keep adding 30 to it see if subsequent 5 numbers are prime, or keep adding 60 to it and verify if subsequent numbers are prime.

We can be a little more scientific about this as well. Now, with common difference 30, we have taken care of 2, 3 and 5. So, the numbers in the AP will not be multiples of these 3. But when you try this out, we realize that we keep running into multiples of 7. So, let us see if we can avoid this.

30 divided by 7 leaves a remainder 2. So, if our prime a leaves a remainder 5 on division by 7 (Like 19), then a + d will be a multiple of 7. Let us build on this. If our prime a leaves a multiple of 3 on division by 7 (like say 17), then a + 2d will be a multiple of 7. If our first prime leaves a remainder 1 on division by 7, then a + 3d will be a multiple of 7 (Eg. 28 ). If the remainder were 6, then a + 4d will be a multiple of 7 (Eg. 13). If the remainder were 4, then a + 5d would be a multiple of 7. {Eg 11}. So, if we pick the common difference as 30, then the first prime should leave a remainder of 2 on division by 7. This is when a + d, a + 2d, a + 3d, a + 4d, and a + 5d can be guaranteed non-multiples of 7. So, start from 23, 37, 79, 107, 149 etc and keep adding 30.

Likewise, for the common difference of 60, the starting point should be a prime that leaves a remainder of 4 on division by 7. So, look at 11, 53, 67, 109 as starting points and keep adding 60. Somewhere we will get lucky. I am not going to give the exact answer. Sooner or later, Karthik will add that on the comments section. Karthik stared long and hard at lists of primes and literally willed an AP to jump out of them.

Think about this. If we had to have 7 prime numbers in an AP, what should be the common difference?

1. We are looking at a prime… To find the starting point.. Lets divide that prime by 7

1-6 are the reminders possible..! But if I take common difference as 60 whose reminder is 4 when divided by 7. Considering 7k+x is the first digit.

Now 7k+1…. 7k+3 and 7k+5, 7k+6 will reach the multiple of 7 before I could add 5 more 4s! So I need to start with 7k+4 where I can add 5 4s and still don’t reach the multiple of 7

(But by the 7th term of AP I will reach that.. So 7th term is na multiple of 7)

IN 7k+4 as first term..

Term reminder when divided by 7

1 4

2 1

3 5

4 2

5 6

6 3

Not a multiple of 7 in all!

2. And if I am looking at an AP of seven terms, then the common difference has to be a multiple of 2,3,5&7.

So it will be 210, 420, 630…