Can a modulus be negative?

% can be negative as it is the remainder operator, the remainder after division, not after Euclidean_division. Since C99 the result may be 0, negative or positive.

 // a % b
 7 %  3 -->  1  
 7 % -3 -->  1  
-7 %  3 --> -1  
-7 % -3 --> -1  

The modulo OP wanted is a classic Euclidean modulo, not %.

I was expecting a positive result every time.

To perform a Euclidean modulo that is well defined whenever a/b is defined, a,b are of any sign and the result is never negative:

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

modulo_Euclidean( 7,  3) -->  1  
modulo_Euclidean( 7, -3) -->  1  
modulo_Euclidean(-7,  3) -->  2  
modulo_Euclidean(-7, -3) -->  2   

According to C99 standard, section 6.5.5 Multiplicative operators, the following is required:

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

Conclusion

The sign of the result of a remainder operation, according to C99, is the same as the dividend's one.

Let's see some examples (dividend / divisor):

When only dividend is negative

(-3 / 2) * 2  +  -3 % 2 = -3

(-3 / 2) * 2 = -2

(-3 % 2) must be -1

When only divisor is negative

(3 / -2) * -2  +  3 % -2 = 3

(3 / -2) * -2 = 2

(3 % -2) must be 1

When both divisor and dividend are negative

(-3 / -2) * -2  +  -3 % -2 = -3

(-3 / -2) * -2 = -2

(-3 % -2) must be -1

6.5.5 Multiplicative operators

Syntax

1. multiplicative-expression:
   • cast-expression
   • multiplicative-expression * cast-expression
   • multiplicative-expression / cast-expression
   • multiplicative-expression % cast-expression

Constraints

2. Each of the operands shall have arithmetic type. The operands of the % operator shall have integer type.

Semantics

3. The usual arithmetic conversions are performed on the operands.

4. The result of the binary * operator is the product of the operands.

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. In both operations, if the value of the second operand is zero, the behavior is undefined.

6. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded [1]. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

[1]: This is often called "truncation toward zero".

I believe it's more useful to think of mod as it's defined in abstract arithmetic; not as an operation, but as a whole different class of arithmetic, with different elements, and different operators. That means addition in mod 3 is not the same as the "normal" addition; that is; integer addition.

So when you do:

5 % -3

You are trying to map the integer 5 to an element in the set of mod -3. These are the elements of mod -3:

{ 0, -2, -1 }

So:

0 => 0, 1 => -2, 2 => -1, 3 => 0, 4 => -2, 5 => -1

Say you have to stay up for some reason 30 hours, how many hours will you have left of that day? 30 mod -24.

But what C implements is not mod, it's a remainder. Anyway, the point is that it does make sense to return negatives.

It seems the problem is that / is not floor operation.

int mod(int m, float n)
{  
  return m - floor(m/n)*n;
}