# 1976 AHSME Problems/Problem 15

## Problem 15

If $r$ is the remainder when each of the numbers $1059,~1417$, and $2312$ is divided by $d$, where $d$ is an integer greater than $1$, then $d-r$ equals $\textbf{(A) }1\qquad \textbf{(B) }15\qquad \textbf{(C) }179\qquad \textbf{(D) }d-15\qquad \textbf{(E) }d-1$

## Solution

We are given these congruences: $1059 \equiv r \pmod{d} \qquad$ (i) $1417 \equiv r \pmod{d} \qquad$ (ii) $2312 \equiv r \pmod{d} \qquad$ (iii)

Let's make a new congruence by subtracting (i) from (ii), which results in $$358 \equiv 0 \pmod{d}.$$ Subtract (ii) from (iii) to get $$895 \equiv 0 \pmod{d}.$$

Now we know that $358$ and $895$ are both multiples of $d$. Their prime factorizations are $358=2 \cdot 179$ and $895=5 \cdot 179$, so their common factor is $179$, which means $d=179$.

Plug $d=179$ back into any of the original congruences to get $r=164$. Then, $d-r=179-164= \boxed{\textbf{(B) }15}$. ~jiang147369

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 