The remainder problem

The description of this puzzle really cracks me up (Dudeney, Strand Magazine, January 1924).

Health risks aside, how do we find the maximal integer d such that (480608 % d) = (508811 % d) = (723217 % d)?

The solution

A good puzzle strategy is to try to simplify the problem. This particular puzzle is equivalent to solving:

• 508811 % d = 480608 % d
• 723217 % d = 480608 % d.

(we get 508811 % d = 723217 % d by the transitive property of equality).

This in turn is equivalent, by linearity of the “modulo d” operation, to:

• (508811 - 480608) % d = 0
• (723217 - 480608) % d = 0.

d is now a proper divisor of these new integers. We have eliminated the unknown shared remainder. And, with quantities related to zero, we have a lot more opportunities for cancellation. The problem is now solvable by a classic algorithm.

You might give the problem a try before we share the finished solution.

Illustration from The Canterbury Puzzles, by Henry Ernest Dudeney

Finishing it

The largest solution to this is the greatest common divisor, written as gcd(508811 - 480608, 723217 - 480608). All other solutions are proper divisors of this greatest common divisor.

To get the specific number we run Euclid’s algorithm; either with pencil and paper, or using a calculator such as R.

# our data
a <- 508811 - 480608
b <- 723217 - 480608

# run Euclid's algorithm
while((a!=b) && (a>=0) && (b>=0)) { 
  while((a>=b) && (b>=0)) {a <- a - b}
  while((b>=a) && (a>=0)) {b <- b - a}
}

# solution
max(a, b)
# 79

# confirm solution
723217 %% 79
# 51
508811 %% 79
# 51
480608 %% 79
# 51