largest integer which gives same modulus result
Hi, if we have a set of positive integers then how can one find the largest positive integer say M such that we get same result on taking modulus operation of each integer in the set with M? E.g if the given set is 12,16,18,22 then then M would be 2 , as 12%2 == 16%2 == 18%2==22%2 . Do we need to find the LCM of the numbers in set ? Thanks.
Re: largest integer which gives same modulus result
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.