Why does (a - b) % m sometimes come out negative?

In C, C++, Java and JavaScript the % operator takes the sign of the left operand, so a negative difference gives a negative remainder. Writing ((a - b) % m + m) % m forces the result into 0..m-1. Python already returns a non-negative value.

Which operations distribute over the modulus?

Addition, subtraction and multiplication: (a + b) % m equals ((a % m) + (b % m)) % m, and likewise for the other two. Division does not distribute and needs a modular inverse.

Why do problems ask for the answer modulo 1000000007?

It keeps every intermediate value inside a 64-bit integer, so the result is well defined without big integers, and because the modulus is prime, modular inverses exist for every non-zero value.

Modular Arithmetic

Modular arithmetic is arithmetic on a circle (clock arithmetic), where numbers wrap around after reaching the modulus.

(14 + 5) MOD 12 · RING OF 12

WRAPPED

Start at 14 mod 12 = 2. The number line is bent into a ring of 12 positions, so every value lands on one of them.

Step 1 of 5: move forward one to 3.

Mod

Intuition

Imagine a clock. If it's 10 o'clock and you add 5 hours, it becomes 3 o'clock, not 15. This is arithmetic modulo 12. Modular arithmetic is simply "arithmetic with cycles".

Concept

Modulo Operator (%): Returns the remainder of division. A % M = R means A = k*M + R.
Addition: (A + B) % M
Subtraction: (A - B) % M. In code, often written as ((A - B) % M + M) % M to handle negative results.
Multiplication: (A * B) % M. Can be visualized as repeated addition on the cycle.

How it Works

Properties:

(A + B) % M = ((A % M) + (B % M)) % M
(A * B) % M = ((A % M) * (B % M)) % M
(A - B) % M = ((A % M) - (B % M) + M) % M

Step-by-Step Breakdown

Watch the visualization:

The circle represents numbers 0 to M-1.
Adding moves clockwise.
Subtracting moves counter-clockwise.
Multiplication is visualized as repeated addition (jumps) on the circle.

When to Use

Cryptography (RSA, Diffie-Hellman).
Hash functions (array indexing).
Cyclic problems (days of week, rotating arrays).
Preventing integer overflow in competitive programming (calculating modulo 10^9 + 7).

When NOT to Use

When exact values matter, not just remainders.
Standard continuous mathematics.

How to Identify

"Return result modulo 10^9 + 7", "Cyclic array", "Divisibility rules", "Periodic Pattern".

Sample Problems

Subarray Sums Divisible by K

Use prefix sums and modular arithmetic.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Sieve of Eratosthenes

Fast Exponentiation