1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about prime numbers

  1. May 23, 2015 #1
    1. The problem statement, all variables and given/known data
    Prove that there are infinitely many prime numbers written ##ak+b##, with ##a,b,k## integers greater than 1

    2. Relevant equations


    3. The attempt at a solution

    Please could you tell me if you agree with that proof ?

    By contradiction:
    Assume that there is an integer ##k## such that ##ak+b## is the greatest prime number of that sort. Then for any ##n > k##, there are ##(u,v)\in \mathbb{N}^\star## such that ##an+b = uv ##. Take ##n = k + u ##, therefore ## ak + b = u (v-a) ##, which contradicts the fact that ##ak+b## is prime.
     
  2. jcsd
  3. May 23, 2015 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Now you basically "proved" that any ##an+b## where ##n>k##is prime.
     
  4. May 23, 2015 #3
    Oh ok I see my mistake, I can't chose ##n## once ##u## is set. Thank you, I'll try something else
     
  5. May 23, 2015 #4
    I haven't made much progress on this one...
    I can show that there are infinitely many primes written ## ak + 1 ##, ##a## even. If you assume that ## ak_0 + 1 ## is the greatest prime, then ## N = a (ak_0+1)! + 1 ## is compound and has a prime divisor ##p## that must be less than ## a (ak_0 + 1)! ##. In that case, ## p## divides ##N## and ##a(ak_0+1)!##, so it divides 1. contradiction.
     
  6. May 23, 2015 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Why must ##p## divide ##a(ak_0+1)##?
     
  7. May 23, 2015 #6
    if ##p## is less than ##a(ak_0+1)!## it divides it
     
  8. May 23, 2015 #7
    Oh no it doesn't work !!!
    I don't know, this problem is too hard for me
     
  9. May 23, 2015 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The proof usually requires some fairly difficult analytic number theory. (And the result is only true if ##\text{gcd}(a,b)=1##).
     
  10. May 23, 2015 #9
    Thank you for the info.
    The one line problem statement looked harmless at first, but I literally lost my time with this problem ;-)
     
  11. May 24, 2015 #10
    @micromass:
    I'm sorry to bother you again, but I think the same idea would work just fine with ## N = (ak_0 +1)! +1 ##, because one can factorize ##a## out of the factorial so that N belongs to the set ##\{ ak+1 , k\ge 1 \}##. Right ?
     
  12. May 24, 2015 #11

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    OK, ##N## is of the form ##ak+1##. So how does that prove anything?
     
  13. May 24, 2015 #12
    If you assume that ##ak_0 +1## is the greatest prime of the form ##ak+1##, then ##N## which also has the form ##ak+1## and is greater than ##ak_0 + 1 ## must be compound. So there is a prime number ##p## that divides ##N## and that is not equal to ##N##.
    But we must have ##p \le N-1 = (ak_0 +1)! ##. In that case ##p## is a factor in ##(ak_0 +1)!##, so that it divides it. But ##p | N ## and ##p| (ak_0+1)! ## implies that ##p | 1##, which is impossible for a prime number. Therefore ##N## is prime and there are infinitely many primes of the form ##ak+1##
     
  14. May 24, 2015 #13

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Why would ##p## be a factor in ##(ak_0 +1)!##
     
  15. May 24, 2015 #14
    Because it is smaller than it
     
  16. May 24, 2015 #15

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    ##5## is smaller than ##3!## and doesn't divide it.
     
  17. May 24, 2015 #16
    OOOOOOOOOK, I get it :-)
     
  18. May 24, 2015 #17
    @micromass
    I was completely wrong, ##N## and ## (ak_0 +1)! ## are relatively prime (Bezout), and ## p | N ## so ##p## and ##(ak_0+1)!## are relatively prime. Which is the same as saying that ##p## does not divide ##(ak_0+1)!##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Question about prime numbers
  1. Prime Numbers (Replies: 3)

Loading...