I know how to solve mod using division i.e.
$$11 \mod 7 = 4$$
For this I did a simple division and took its remainder:
i.e.
$$11 = 7 \cdot 1 + 4$$
Where $11$ was dividend, $7$ divisor, $1$ quotient and $4$ was remainder.
But I have a problem with:
$$-11 \mod 7 = 3$$
How come it is $3$? I cannot figure this out using division but if it is possible I would like to.
Best Answer
It's $3$ because $-11 = 7(-2) + 3$.
Another way to see this is to take $-11$ and keep adding $7$ to it until you get a positive number. This works because, if you're working modulo $7$, then adding $7$ is the same as not changing the number (modulo $7$). So:
$-11 + 7 \equiv -11 \pmod 7$, and $-11 + 7 = -4$. Therefore $-4 \equiv -11 \pmod 7$. Well, we're still negative. Let's do it again:
$-4 + 7 \equiv -11 \pmod 7$, and $-4 + 7 = 3$. Therefore, $3 \equiv -11 \pmod 7$.
Or, equivalently, $-11 \equiv 3 \pmod 7$.
How do we know to use $-2$? Let's recall how it works with positives first.
If you want to evaluate $31 \pmod 7$, you first recognize that $31 = 28 + 3 = 7 \cdot 4 + 3$. Therefore $31 \equiv 3 \pmod 7$. What did we do here? We found the largest multiple of $7$ that's less than or equal to $31$.
Alternatively, with division, you can evaluate $31/7 \approx 4.429$. The largest integer less than or equal to this is $4$. Therefore $31 = 7 \cdot 4 + \text{some number}$, where your goal is to determine what $\text{some number}$ is.
This same exact process applies for negative numbers.
If you want to evaluate $-11 \pmod 7$, you need the largest multiple of $7$ that's less than or equal to $-11$. This is $-14$. And $-14 + 3 = -11$, therefore your answer is $3$.
Alternatively, with division, you can evaluate $-11/7 \approx -1.571$. The largest integer less than or equal to this is $-2$. Therefore $-11 = 7 \cdot (-2) + \text{some number}$, where your goal is to determine what $\text{some number}$ is.