# Dudeney’s Remainder Problem

**R – Win Vector LLC**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

## 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

**leave a comment**for the author, please follow the link and comment on their blog:

**R – Win Vector LLC**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.