Are There Any Pairs (P,Q) With All Composite Integers Modulo Q?

[ACG]

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

 

[robert Ihnot]

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.

 

[d_leet]

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.

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.

 

[Moo Of Doom]

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.

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.