CODEWITHSUNDEEP
mathcomputer-sciencemodulonumber-theory
Chad Mourning
Chad Mourning

Reputation: 619

Finding the largest modulus of congruence for two integers?

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?

Upvotes: 2

Views: 1395

Answers (1)

lurker
lurker

Reputation: 58254

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.)

Upvotes: 4

Related Questions