The % operator in C is not the modulo operator but the remainder operator.

Modulo and remainder operators differ with respect to negative values.

With a remainder operator, the sign of the result is the same as the sign of the dividend (numerator) while with a modulo operator the sign of the result is the same as the divisor (denominator).

C defines the % operation for a % b as:

  a == (a / b * b) + a % b

with / the integer division with truncation towards 0. That's the truncation that is done towards 0 (and not towards negative inifinity) that defines the % as a remainder operator rather than a modulo operator.

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.

Using % a second time in @sellibitze's and @liquidblueocean's answers probably won't be as slow as % tends to be in general, because it boils down to either one subtraction of b or none. Actually, let me just check that...

int main(int argc, char **argv) {
    int a = argc;    //Various tricks to prevent the
    int b = 7;       //compiler from optimising things out.
    int c[10];       //Using g++ 4.8.1
    for (int i = 0; i < 1000111000; ++i)
        c[a % b] = 3;
        //c[a < b ? a : a-b] = 3;
    return a;
}

Alternatively commenting the line with % or the other line, we get:

• With %: 14 seconds

• With ?: 7 seconds

So % is not as optimised as I suspected. Probably because that optimisation would add overhead.

Therefore, it's better to not use % twice, for performance reasons.

Instead, as this answer suggests and explains, do this:

int mod(int k, int n) {
    return ((k %= n) < 0) ? k+n : k;
}

It takes a bit more work if you want it to work properly for negative n too, but that's almost never necessary.

Not sure how familiar with modular arithmetic you are, but deriving a few basic results and appealing directly to definitions, those results become much more obvious:

Proposition 1.1: For any two integers $a,b$, with $a \gt 0$, there exist integers $q,r$ such that $$ b=qa +r , \qquad 0 \leq r \lt a.$$

Proof:

Consider the rational number $\frac{b}{a}$. There exists a unique integer $q$ such that $$q \leq \frac{b}{a} \lt q +1$$ $$\implies qa \leq b \lt qa + a$$ $$\implies 0 \leq b - qa \lt a,$$ and, letting $r=b - qa $, the result follows.

$\square$

Definition 1.2: Let $a,b \in \mathbb{Z}$. We say $a$ divides $b$, if, for some integer $c$, $$b=ac.$$

$\quad$

Definition 1.3: Let $m$ be a positive integer. For any $a,b \in \mathbb{Z}$, if $m$ divides $a-b$, we write $a \equiv b \pmod{m}$.

$\quad$

Proposition 1.4: Every integer is congruent to exactly one of the integers $0,1,2 \cdots, m-1$ $\pmod{m}$.

Proof:

Note that $$a \equiv b \pmod{m} \iff a-b=qm,$$ for some integer $q$, and so Proposition 1.4 follows immediately from Proposition 1.1.

$\square$

Evaluating the example in your question, by Proposition 1.4, $-8$ is congruent to exactly one of the integers $0,1, 2,3,4,5, \pmod{6}$.

Now, it is clear that $-8=-2 \cdot 6 + 4$ and so $$-8 \equiv 4 \pmod{6},$$ or, in your notation $$-8\pmod{6}=4.$$

Your suffering stems from embracing the illusion that % is a "modulo" operator. In truth, it is a remainder operator (C11 §6.5.5):

The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder

Reject the illusion and accept the truth, and the behavior of the operator will become clear (Ibid.):

If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a

In your case, a/b is -4/3, which is -1, hence representable. So a%b satisfies:

(a/b)*b + a%b =  a
(-1)*3  + a%b = -4
  -3    + a%b = -4
          a%b = -1