Sunday, December 09, 2012

Modular Mathematics

A friend had a question to determine the largest integer divisor that would yield the same integer remainder for three given integer values. The provided example problem was not too difficult to solve by inspection, but I wanted to know the "why" behind it (and to know that I was correct without writing a quick bit of code to prove it). If you're interested, the three given values were 364, 414, 539. 


It's tempting to start with prime factoring, but that is not the path to success in this case, at least not yet...

After spending quite some time staring at and playing with numbers, we figured out how to solve for a special case where b > a > b/2. In that case, the greatest modulus always appeared to be (b-a). But, this broke down if a < b/2. An example we used was 353, 262, and 54.  353-262 = 91. 



Checking the answer: 353 / 91 = 3 + 80/91   and 262 / 91 = 2 + 80/91


Great, but 262 - 54 = 208, so now what...  Sure it "works" with 262 = 1 + 54/208 and 54 / 208 = 0 + itself. But, not a useful exercise for the general problem.

Then we got close to the answer, looking at the intervals but not seeing their relationship, here's a teaser:

353  - 262 = 91
353 - 54 = 299
262 - 54 = 208


We were close, but got distracted because we are well trained to factor the starting vales.  I postulated that we should pull out additional multiples of 54 and see what happened.  

353 - (6 * 54) = 29 
262 - (4 * 54)  = 46


This was as big of a red herring as factoring the values themselves. We care about the bloody remainder, but if we factor, it's zero and the answer is pretty boring. It was hard to get out of this box. In our special case where b > a > b/2, it was always true that b mod (b-a) and a mod (b-a) were congruent, the following was also true in this case:


(b / (b-a)) - (a / (b-a)) = 1

In retrospect, this seems obvious, as it quickly decomposes to an identity relationship: b-a clearly equals b-a.

-=-=-=-=-=-=-=-

The benefit was that I then realized that the congruency should hold if (b/m) - (a/m) = n, where n is any integer. (And similarly, if there are three numbers c > b > a, then c/m - b/m = i and c/m - a/m = j must also be true, where i and j are also integers). 

Rephrasing using a modulo function, a mod(m) must be congruent to (a + mi) mod(m) for any integer i.


So, If b can be expressed as (a+mi), then the common modulus will be m. This means that the greatest common divisor associated with the intervals we calculated must be my modulus. So, we need to factor 91, 299, and 208: 

91 = 7 * 13 
208 = 2^4 * 13 
299 = 13 * 23



13 is the only common factor, and therefore the GCD, and therefore my modulus. Testing this solution:



353 / 13 = 27 + 2/13
262 / 13 = 20 + 2/13
54 / 13 = 4 + 2/13



Applying this methodology to the original problem:

539 - 414 = 125 = 5^3
539 - 364 = 175 = 5^2 * 7
414 - 364 = 50 = 2 * 5^2
The GCD is therefore 5^2 (aka 25) and the remainder is clearly 14 by simple inspection.