Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime question

  1. Mar 25, 2007 #1

    ACG

    User Avatar

    Hi! I was thinking about primes and have a bit of a question. I apologize if this is too easy or obvious -- I haven't thought much about it.

    Take two relatively prime numbers, P and Q. P < Q, and P is not prime.

    How many pairs (P,Q) are there so that ALL positive integers which are P modulo Q are composite? I couldn't think of any. For instance,

    (6,11)

    won't work because 17 is prime.

    (8, 11) will choke on 19, and (8, 13) will choke on 47.

    I know primes become much rarer when you get further up the number line. But do they get rare enough at some point for this to happen? I would suspect not, but I'm curious if there's a proof.

    Thanks in advance,

    ACG
     
  2. jcsd
  3. Mar 25, 2007 #2
    ACG:I know primes become much rarer when you get further up the number line. But do they get rare enough at some point for this to happen? I would suspect not, but I'm curious if there's a proof.


    No, it does not happen. There is something called Dirichlet's Theorem. Given an two relatively prime integers, (a,b)=1, the arithmetical series a+b, a+2b, a+3b.....contains an infinite number of primes.
     
  4. Mar 25, 2007 #3
    That series may contain an infinite number of primes, but that does not say that each term in that series is a prime. Consider a=4 and b=9, a+4b has a factor of 4 and hence is not prime.

    To the original poster what do you mean by rare enough? For every natural number n you can find a sequence of n consecutive compositie numbers.
     
  5. Mar 25, 2007 #4
    But ACG wasn't looking for each term being prime. He was looking for each term being composite, so one prime is enough to shatter that idea. Since every such series contains at least one prime (an infinite amount), that answers his question thoroughly.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prime question
  1. Prime Question (Replies: 13)

Loading...