Maths and Computing:

---

Enter a modulus:

---

---

Workings for:

---

Log

Operations

---

Modulo Maths

Modulo Operation

The modulo operation returns the remainder when an integer is divided by another integer

Consider a (mod n) and b (mod n)

• a, b and n must be integers
• a mod n returns a value between 0 and (n-1)

Modulo Operation Example

• 19 mod 4 = 3 (19/4 = 4 remainder 3)
• 55 mod 17 = 4 (55 = 3 × 17 + 4)

Calculations using the Modulo Operation

Addition and Multiplication can be simplified by applying the modulo operation to each value in the calculation, and then again to the result.

• (a + b) mod n = (a mod n + b mod n) mod n
• (a × b) mod n = (a mod n × b mod n) mod n

Calculating a^r can be simplified by applying the modulo operation to a and/or to factors of a^r

• a^r mod n = (a mod n)^{r mod n}
• a^pq mod n = (a^p mod n × a^q mod n) mod n

Modulo Calculations Examples

1. (8 + 19) mod 5 = (8 mod 5 + 19 mod 5) mod 5
   = (3 + 4) mod 5
   = 7 mod 5
   = 2
2. (8 × 19) mod 5 = (8 mod 5 × 19 mod 5) mod 5
   = (3 × 4) mod 5
   = 12 mod 5
   = 2
3. 8⁶ mod 5 = (8 mod 5)⁶ mod 5
   = 3⁶ (mod 5)
   = 729 (mod 5)
   = 4
4. 7⁴¹ mod 5 = (7 mod 5)⁴¹ mod 5
   = 2⁴¹ mod 5
   = ((2⁴)¹⁰ × 2) mod 5
   = ((16 mod 5)¹⁰ × 2) mod 5
   = (1¹⁰ × 2) mod 5
   = 2 mod 5 = 2

Modulo Congruence

Two numbers x and y are congruent for a given modulus n, when:

• a mod n = b mod n

Congruence is written using the equivalence sign: ≡

• a ≡ b (mod n)