Finding the largest modulus of congruence for two integers?
-
11-02-2021 - |
Question
Given two integers is there an easy way to find the largest modulus of congruence for them? i.e. a % n == b %n, Or even to enumerate all of them? Obviously, I could try every value less than them, but it seems like there should be an easier way.
I tried doing something with gcds, but then you just get things where a % n == b % n == 0, which isn't as cool as I was hoping for, and I'm pretty sure this isn't necessarily the largest n.
Any ideas?
Solution
If a and b are the numbers, then we consider:
a = nx + r
b = ny + r
Where n is the modulus we want to find, and r is the common remainder. So,
a - b = n(x - y)
Maximum n is achieved with x - y = 1. So,
n = a - b
(If I understood the question correctly.)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow