Arithmetic

Modular Arithmetic

A clock reads 10, and in 5 hours it will say 3, not 15, that's modular arithmetic in action. The same mathematics protects internet passwords, bank transfers, and state secrets. Remainder arithmetic is one of the most practical branches of number theory.

  • **Cryptography:** RSA, digital signatures
  • **Hashing:** data distribution, checksums
  • **Everyday life:** clocks, days of the week, schedules

The Modulo Operation

The modulo operation underpins almost every secure transaction online: RSA encryption (Rivest-Shamir-Adleman, 1977) relies on arithmetic modulo 2048-bit numbers, and elliptic-curve cryptography on the curve secp256k1 (used by Bitcoin since 2009) operates modulo a 256-bit prime. Roughly 95 percent of internet traffic by 2024 is protected by modular arithmetic of this kind.

The **mod** operation (modulo) returns the remainder after division. It is "cyclic" arithmetic: after a certain value, numbers start over.

**The mod operation:** a mod n = remainder when a is divided by n 17 mod 5 = 2 (because 17 = 3×5 + 2) 23 mod 7 = 2 (because 23 = 3×7 + 2)

Modular arithmetic is arithmetic "in a circle". After n−1 comes 0 again, just like on a clock face.

What is 47 mod 7?

Congruences

Two numbers are **congruent modulo n** if they have the same remainder when divided by n. Written as: a ≡ b (mod n).

**The ≡ symbol (congruence):** Don't confuse it with equality (=)! 17 ≠ 2, but 17 ≡ 2 (mod 5) These are different numbers but "equal modulo 5".

Congruences are the language of number theory. They let us work with infinite sets by looking only at remainders.

0

1

Sign In

Which statement is correct?

Modular Operations

Addition, subtraction, and multiplication work naturally with modular arithmetic. Reducing modulo at each step gives the same result as reducing once at the end.

**Practical application:** RSA cryptography uses these operations: m^e mod n (encryption) c^d mod n (decryption) Where n is the product of two large prime numbers.

Modular exponentiation is the foundation of modern cryptography. Easy to compute, but practically impossible to reverse (find the exponent).

What is (7 × 8) mod 10?

Applications

Modular arithmetic surrounds us: clocks, days of the week, hash functions, checksums, cryptography.

**Chinese Remainder Theorem:** If n₁, n₂, ..., nₖ are pairwise coprime, then the system of congruences: x ≡ a₁ (mod n₁) x ≡ a₂ (mod n₂) ... has a unique solution modulo n₁×n₂×...×nₖ.

Modular arithmetic is a bridge between school mathematics and modern cryptography. Bank transfers and HTTPS handshakes are protected by exactly these ideas (RSA, ECDSA).

The remainder when dividing by n is always less than n

The remainder when dividing by n belongs to the set {0, 1, ..., n-1}

This is actually a correct statement, but it's often forgotten! The remainder is always non-negative and strictly less than the divisor. 17 mod 5 = 2 (not -3, even though 17 = 4×5 + (-3) is arithmetically valid). By convention, the remainder is always from 0 to n-1.

Today is Monday. What day of the week will it be in 1000 days?

Key Ideas

  • a mod n, remainder when a is divided by n
  • a ≡ b (mod n), same remainders
  • +, -, × work naturally modulo n
  • Foundation of modern cryptography

Related Topics

Modular arithmetic is connected to number theory:

  • Divisibility — Remainders and division
  • LCM — Chinese Remainder Theorem
  • Prime Numbers — RSA cryptography

Вопросы для размышления

  • Why is modular exponentiation the foundation of cryptography?
  • How is modulo 7 related to days of the week?
  • Why is division modulo harder than other operations?

Связанные уроки

  • dm-14
  • crypto-02-modular-arithmetic
Modular Arithmetic