# How can I find a mod with negative number? [duplicate]

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.

• Just add $2\times 7$ to $-11$. Commented Mar 9, 2017 at 19:10
• The rest of division is always non-negative. Then $-11=7(-2)+3$ give your answer. Commented Mar 9, 2017 at 19:11
• $-11$ is $3$ more than a multiple of $7$. Commented Mar 10, 2017 at 1:49
• There are different interpretations of modulus torstencurdt.com/tech/posts/modulo-of-negative-numbers Commented Feb 1, 2022 at 12:36
• Commented Sep 15, 2023 at 19:01

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.

• Why would I multiply it with $-2$? Okay, because $-14$ would be smaller than $-11$? Commented Mar 9, 2017 at 19:12
• @user963241, the same reason you'd multiply it by $4$ if you were evaluating $31 \pmod 7$: It's what works. Or are you asking how to know you need to use $-2$?
– user307169
Commented Mar 9, 2017 at 19:14
• Yes, that's what I am asking how to decide on $-2$. My guess that on negative numbers we go for smaller numbers? Commented Mar 9, 2017 at 19:15
• @user963241 For +ve numbers you find largest value less than the number like for $9/2$ you will find $4 * 2 = 8$, Same for -ve, like for $-9/2$ you find the largest number less $-9$ which is $-10$. Apply to your question you get $-14$ because $-7$ is larger than $-11$.
– user312097
Commented Mar 9, 2017 at 19:15
• @A---B: Can you please edit your comment? I think it needs some fixes. Commented Mar 9, 2017 at 19:19

As others have said, it is because $$−11 = 7(−2) + 3$$

However, I believe all other answers failed to mention that you need(ed) to define the division algorithm FIRST.

The division algorithm is defined as Euclidean division, where given two integers a and b, with b ≠ 0, there exist unique integers q and r such that

$$a = bq + r$$ and $$0 \leq r < |b|$$

therefore, $$r$$ MUST always be positive and numbers modulo fit into this definition therefore, the mod of a number is never negative.

• "The division algorithm is defined as Euclidean division" well. I would be careful. Given two positive numbers a and n, a modulo n (often abbreviated as a mod n) is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor. Not in the case of negative numbers. Modulo is not a division, it is wrapping cyclicly. This example −11(mod7) cannot be defined as division as in the case of two positive numbers a and n. How would you visualize it? 11 mod 7 as division is easy It is 1.571 ( rounding 7 x 0.571 = 4). In the case of -11 /7 -1.571 is -4.. and not 3. Commented Mar 28 at 19:58
• Part 2. You need to look at it as a cyclical wrapping. a mod n where n signifies cycle length (12 for an hour in clock, 24 hours a day, 12 months a year, etc). And a is for iterating over the cycle how many times! In the case of -11 mod 7 you have a cycle (1,2,3,4,5,6,7) but you are counting back (due to the minus!). Your starting point is 7 then so start counting 1(6),2(5).....6(1),7(7),8(6),9(5),10(4) and finally we arrived at to zero i.e 11(3). P.S. I incremented the iterator but in this case, you should count backward from 11. Commented Mar 28 at 19:58
• Part 3. -9 mod -2 = -1 therefore a=bq +r != 0≤r<|b| Commented Mar 28 at 20:06

I regard the negative remainder as an overshoot on the division operation. Since by definition the remainder needs to be positive, then another operation is required to get the "true remainder".

e.g. $$43=-2 (mod\;5)$$

You can express as above $$43 = 8 \times 5 + 3$$, or $$43 = 9 \times 5 - 2$$. In this last expression you are "short" $$2$$ to complete the module $$5$$, but you are "over $$3$$" to the previous complete module $$40$$. Hence the positive remainder is $$5-2 =3$$ (i.e. Module plus the negative remainder). Operationally would be to use the standard division, but note that the remainder is negative, then you need to do the last operation to get the positive remainder.

In your example: $$-11 \;mod\; 7 = 3$$

$$-11/7 = - 1 4/7$$ , My reaction is regard $$4$$ as the remainder. However note that it is really $$-4$$. Hence you need to do the last operation: $$7-4 = 3$$

I apologize for the lack of rigor on my use of definitions, but it's just a way to figure this logically.

• Well, reminder can be negative. But mod is not division indeed Commented Mar 29 at 16:01