Suppose we have two relatively prime numbers, say 18 and 31. LCM has nothing to do with it, but GCF(18, 31) = 1. However, M is not 1. 18 and 31 are congruent mod 13 so M = 13.
Turns out, if we have n numbers, , M should be equal to the GCF of all of the pairwise differences . This is because if M is the largest modulus such that all the are congruent, then for all i,j. Therefore M must be a factor of all the pairwise differences, and the largest such M is the GCF of these differences.