Multiples of prime p occur every p numbers because of the definition of the primes. If the

number k is a multiple of p, then the next multiple of p will be (k+p). Since the least

prime is p=2, k+1 does not share any prime factor with k.

Regards. Jose Brox