Introduction to modular arithmetic (residues)

Question

I have been recently using the book introduction to Number Theory from Art of Problem Solving as I am preparing for the upcoming AMC 10 (I'm an 8th grader).

In section 12.3 problem 12.3.3 it says

Determine the residue of each of the following within the given modulus.

It says $71\pmod{3}$ and that the answer is $71 = 23 \cdot 3 +2$, hence $71 \equiv 2 \pmod{3}$.

Can someone explain why it has to be $71 = 23 \cdot 3 +2$? I'm re-reading the passage but I don't get the fundamental concept of a residue.

The residue is just the remainder. The remainder of $71$ divided by $3$ is $2$. — player3236, Nov 14 '20 at 17:37
Oh sorry I will try using LaTeX next time I post a question. I think I get it now thanks everyone! — QuantumPi, Nov 14 '20 at 17:38
Re: "it has to be", what do you mean by that? What else could it be? Do you know the meaning of (Euclidean) division with (smaller) remainder? (which is what that expression represents). — Bill Dubuque, Nov 14 '20 at 22:33

score 1 · Answer 1 · answered Nov 14 '20 at 17:52

The residue of $a$ in the modulus $n$ is the remainder of the division of $a$ by $b$, hence it must be a number $r$ such that $0\le r<b$.

The “division with remainder” can be written as $a=bq+r$, where $q$ is the quotient and $r$ is the remainder.

In your case, the quotient of the division of $71$ by $3$ is $23$, and $$ 71=3\cdot23+2 $$ Since $m\equiv n\pmod{b}$ means that $m-n$ is divisible by $b$, you surely have $$ 71-2=3\cdot23 $$ and therefore $71\equiv2\pmod{3}$.

It's nothing else than primary school division, written in a slightly different way.

Introduction to modular arithmetic (residues)

1 Answers1