Results 1 to 8 of 8

Math Help - Prime

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    Prime

    Find with proof the longest arithmetic progression, with common difference 6, that contains only primes.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by usagi_killer View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Quote Originally Posted by ynj View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Bingk View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by Bingk View Post
    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+6tis always prime when 0\leq t\leq k-1. But unfortunately, I have chosen 5 when I started to do this problem...
    Last edited by ynj; August 25th 2009 at 06:32 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    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 )
    Follow Math Help Forum on Facebook and Google+

  7. #7
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by Bingk View Post
    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!!!!
    Last edited by ynj; August 25th 2009 at 06:33 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 08:51 AM
  4. why is a prime squared + itself + 1 also a prime
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: November 19th 2010, 08:03 PM
  5. Replies: 6
    Last Post: August 28th 2010, 12:44 AM

Search Tags


/mathhelpforum @mathhelpforum