6k+1 might also be composite. However, it can be prime; a e.g. 6k+3 can literally never be prime, because it will always be divisible by 3. Every prime p > 15

6k+1 might also be composite. However, it can be prime; a e.g. 6k+3 can literally never be prime, because it will always be divisible by 3. Every prime p > 15 can be written as 15k + r, where r = p % 15 is coprime to 15. Put this way, it should be pretty clear what's going going on: gcd(15, r) is necessarily a factor of p, so we need that to be 1. Of course for prime p, gcd(p, q) is necessarily 1 for all q < p.