0
$\begingroup$

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$.)

|cite|improve this question
$\endgroup$
  • $\begingroup$ Keep adding 52 until you get a small positive number.... $\endgroup$ – N. S. Oct 13 '14 at 23:38
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ how did you get the four? $\endgroup$ – Nicole Oct 13 '14 at 23:36
  • $\begingroup$ @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. $\endgroup$ – Nick Oct 13 '14 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.