Here is an exercise: does this generalize from 6 to any M > 2?
The 1 and 5 elements of the (modulo 6) congruence are precisely those which are relatively prime to 6: those two elements that Euler's totient function counts: φ(6) = 2.
It doesn't generalize trivially; there is osmething to puzzle out there. For instance in the case of M = 15, we have 8 being relatively prime to 15. Yet 15k + 8 might be composite (like in the case k = 0).
I may go into it more if I have a bit of time away from other interesting or urgent matters.
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.
The 1 and 5 elements of the (modulo 6) congruence are precisely those which are relatively prime to 6: those two elements that Euler's totient function counts: φ(6) = 2.
It doesn't generalize trivially; there is osmething to puzzle out there. For instance in the case of M = 15, we have 8 being relatively prime to 15. Yet 15k + 8 might be composite (like in the case k = 0).
I may go into it more if I have a bit of time away from other interesting or urgent matters.