Prime

**usagi_killer** · August 25th 2009, 05:11 AM

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

**ynj** · August 25th 2009, 05:33 AM

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.

**Bingk** · August 25th 2009, 08:12 AM

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.

I was just wondering about your proof.

$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

**Opalg** · August 25th 2009, 08:37 AM

Originally Posted by Bingk

I was just wondering about your proof.

$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.

**ynj** · August 25th 2009, 09:08 AM

Originally Posted by Bingk

I was just wondering about your proof.

$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...

**Bingk** · August 25th 2009, 03:31 PM

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

)

**ynj** · August 25th 2009, 05:21 PM

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!!!!

**Bingk** · August 26th 2009, 07:29 AM

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

Thread: Prime

LinkBack

Thread Tools

Display

Prime

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Prove that if n>=2 and not prime, then n has a prime divisor p<=(sq.root)n

Group whose order is a power of a prime contains an element of order prime

why is a prime squared + itself + 1 also a prime

Prove that for every prime p, there exists another prime q such that p and q-1 are...

Search Tags