Pigeonhole principle with primes

490 Views Asked by At

Show that if $n$ and $k$ are positive integers, with $n>1$ and all $n$ positive integers $a, a+k,..., a+(n-1)k$ are odd primes, then $k$ is divisible by every prime less than $n$.

I tried:

$a=p*q_0 = r_0$

$a+k=p*q_1 = r_1$

$a+(n-1)k=p*q_{n-1} = r_{n-1}$

But this is in contradiction with the red marked step:

enter image description here

Next the green step, $p|(a*b)\Rightarrow p|a$ v $p|b$

Is it also true like $p|(a*b) \Leftrightarrow p|a$ v $p|b$

Is this only true for prime numbers?

1

There are 1 best solutions below

2
On

Yes the step in green is true, and yes it’s only true for primes. If $n$ is a composite number such that $n=pq$ then $n|pq$ obviously holds, but $n$ doesn’t divide either $p$ or $q$. For a less trivial counterexample, you can have “mismatched” factors. If $n=pq$ then $n|(pr)(qt)$ for any $r,t$ but unless $q|r$ or $p|t$ you’re not going to have $n|pr\lor n|qt$.