modular arithmetic congruence

Simplify the following congruence: $$−169 \equiv \text{ ?} \mod 52$$ (By simplify, we mean find the smallest non-negative whole number which is congruent to $-169$ modulo $52$.)

Simplify the following congruence:

$$−501 \equiv \text { ?} \mod 213$$ (By simplify, we mean find the smallest non-negative whole number which is congruent to $-501$ modulo $213$.)

• Keep adding 52 until you get a small positive number.... – N. S. Oct 13 '14 at 23:38

If we use division with remainder, we obtain

$$169 = 3 \cdot 52 + 13$$

Multiplying each side of the equation by $-1$ yields

$$-169 = -3 \cdot 52 - 13$$

Hence, $-169 \equiv -13 \pmod{52}$. However, $-13 < 0$, so we add and subtract $52$ to the right side of the equation.

\begin{align*} -169 & = -3 \cdot 52 - 13\\ & = -3 \cdot 52 - 52 + 52 - 13\\ & = -4 \cdot 52 + 39 \end{align*}

Thus, $-169 \equiv 39 \pmod{52}$. Since $0 \leq 39 < 52$, $39$ is the smallest non-negative integer congruent to $-169 \pmod{52}$.

You can apply the same strategy in your second problem.

The smallest, non-negative number which is congruent to $-169$ modulo $52$ is called the least residue of $-169$ modulo $52$.

Note that $-169 + ( 4 \times 52 ) = 39$, so $-169 \equiv 39 \mod 52$.

Try this yourself for the second question.

• how did you get the four? – Nicole Oct 13 '14 at 23:36
• @Nicole Four is the number of times you need to add 52 to -169 to get a positive number. Note that adding any lesser multiple of 52 will leave you with a negative number. – Nick Oct 13 '14 at 23:38