# Math Help - Prime

1. ## Prime

Find with proof the longest arithmetic progression, with common difference 6, that contains only primes.

2. Originally Posted by usagi_killer
Find with proof the longest arithmetic progression, with common difference 6, that contains only primes.
the answer is 5:5 11 17 23 29
Proof:
consider the sequence: $a,a+6,a+12,a+18,a+24$
Then we have $a\equiv a(\mod 5),a+6\equiv a+1(\mod 5),a+12\equiv a+2(\mod 5)$, $a+18\equiv a+3(\mod 5),a+24\equiv a+4(\mod 5)$
But there must be a zero among $a,a+1,a+2,a+3,a+4 \mod 5$.
The only possible situation is $a=5$ and it is actually the case.

3. Originally Posted by ynj
the answer is 5:5 11 17 23 29
Proof:
consider the sequence: $a,a+6,a+12,a+18,a+24$
Then we have $a\equiv a(\mod 5),a+6\equiv a+1(\mod 5),a+12\equiv a+2(\mod 5)$, $a+18\equiv a+3(\mod 5),a+24\equiv a+4(\mod 5)$
But there must be a zero among $a,a+1,a+2,a+3,a+4 \mod 5$.
The only possible situation is $a=5$ and it is actually the case.

$a,a+1,a+2,a+3,a+4 \ (mod 5)$ should indeed have a zero, but how did you get that $a=5$ is the only possible solution? Can't $a$ be any integer (since there are 5 terms there in a +1 arithmetic progression)? For example, if $a=13$ then $a+2 = 13+2 = 15 \equiv 0 \ (mod5)$

Also, why did you consider only the sequence up to $a+24$? Why not also $a+30,a+36,...$?

Also, how come mod 5? (For example, if you use mod 7, and start at a+42 till a+78, you'll get a,a+6,a+5,a+4,a+3,a+2,a+1 mod 7, respectively, and since one of the terms must be congruent to zero mod 7, then we just have to find an appropriate 'a')

P.S. Sorry if I seem like I'm trying to shoot down your proof, it's just that it doesn't seem concrete to me (specially since you limited the sequence already, so we're kind of limiting the progression already), and I am hoping you could enlighten me . Thanks

4. Originally Posted by Bingk

$a,a+1,a+2,a+3,a+4 \ (mod 5)$ should indeed have a zero, but how did you get that $a=5$ is the only possible solution?
The point of ynj's proof is that any arithmetic progression of length 5 (with common difference 6) must contain a multiple of 5. But the only prime multiple of 5 is 5 itself. So the only way to get such a progression to consist entirely of primes is if the sequence starts with 5.

5. Originally Posted by Bingk

$a,a+1,a+2,a+3,a+4 \ (mod 5)$ should indeed have a zero, but how did you get that $a=5$ is the only possible solution? Can't $a$ be any integer (since there are 5 terms there in a +1 arithmetic progression)? For example, if $a=13$ then $a+2 = 13+2 = 15 \equiv 0 \ (mod5)$

Also, why did you consider only the sequence up to $a+24$? Why not also $a+30,a+36,...$?

Also, how come mod 5? (For example, if you use mod 7, and start at a+42 till a+78, you'll get a,a+6,a+5,a+4,a+3,a+2,a+1 mod 7, respectively, and since one of the terms must be congruent to zero mod 7, then we just have to find an appropriate 'a')

P.S. Sorry if I seem like I'm trying to shoot down your proof, it's just that it doesn't seem concrete to me (specially since you limited the sequence already, so we're kind of limiting the progression already), and I am hoping you could enlighten me . Thanks
en..you may wonder how 5 appears..
One thing is certain that our main idea is to prove there always exists an element in every sequence that is divisible by some k.
Then we consider the sequence $a,a+6\mod k,a+12\mod k,...,a+6t\mod k...$.
if k and 6 are not relatively prime, then $\{6t\mod k\}!=\{0,1,...,k-1\}$. Then you can choose some $m\in\{0,1,...,k-1\}-\{6t\mod k\}$, thus my previous proof can not work for $a+k-m$.
So we may assume k and 6 are relatively prime.
then you can choose anything you like until you have found a sequence such that $a+6t$is always prime when $0\leq t\leq k-1$. But unfortunately, I have chosen 5 when I started to do this problem...

6. Ah, okay ... I'm starting to get it now ... Thanks

Sorry, I didn't know that mod could be interpreted that way.

Ah ... it's coming together now ...

6 and k should be relatively prime.

That first occurs when k = 5.

From that statement, we see that any arithmetic progression of length at least 5 (with difference 6) will have a number divisible by 5. That is why you didn't consider more than a+24 since adding a+30 to the sequence will give us 2 numbers that are divisible by 5, and thus at least one will not be prime.

So the only possibility is when 'a' = 5, which gives us ynj's sequence.

Now if we consider a number greater than 5 and relatively prime to 6, we see that we can get an arithmetic progression of longer length, but since it contains a progression of length 5, then there will be a multiple of 5 in the progression, forcing one of the terms to be 5 (the only prime multiple of 5 ....).

Since we are not considering negatives, the sequence must start at 5.

So, we start at 5, and from the first part, confirm that the first 5 terms are indeed prime, and the 6th term is not prime.

Thus 5,11,17,23,29 is the sequence and it's length is 5

Ah ... thank you so much ... I feel like my brain is growing hehehe. (Just to be sure, no sarcasm there, I really am appreciative ... I took a number theory class before, but I felt unfulfilled ... what I basically learned was critical thinking ... we didn't even cover solving congruences , and I'll leave it at that, cuz the rest is worse, hehe )

7. Originally Posted by Bingk
Ah, okay ... I'm starting to get it now ... Thanks

Sorry, I didn't know that mod could be interpreted that way.

Ah ... it's coming together now ...

6 and k should be relatively prime.

That first occurs when k = 5.

From that statement, we see that any arithmetic progression of length at least 5 (with difference 6) will have a number divisible by 5. That is why you didn't consider more than a+24 since adding a+30 to the sequence will give us 2 numbers that are divisible by 5, and thus at least one will not be prime.

So the only possibility is when 'a' = 5, which gives us ynj's sequence.

Now if we consider a number greater than 5 and relatively prime to 6, we see that we can get an arithmetic progression of longer length, but since it contains a progression of length 5, then there will be a multiple of 5 in the progression, forcing one of the terms to be 5 (the only prime multiple of 5 ....).

Since we are not considering negatives, the sequence must start at 5.

So, we start at 5, and from the first part, confirm that the first 5 terms are indeed prime, and the 6th term is not prime.

Thus 5,11,17,23,29 is the sequence and it's length is 5

Ah ... thank you so much ... I feel like my brain is growing hehehe. (Just to be sure, no sarcasm there, I really am appreciative ... I took a number theory class before, but I felt unfulfilled ... what I basically learned was critical thinking ... we didn't even cover solving congruences , and I'll leave it at that, cuz the rest is worse, hehe )
em..We may generalize this problem to be "common difference x". Then the answer must be the smallest prime number relatively prime to x!! Then you just have to check it!!!!

8. You know, you're probably right, but "Then the answer must be the smallest prime number relatively prime to x!!" is a big jump for me . But thanks again, it's making more sense now