# Modular Arithmetic

Mathematics I · Arithmetic and Number Theory · https://tryals.app/learn/mathematics-i/modular-arithmetic

## Arithmetic That Wraps Around

**Modular arithmetic** is the mathematics of things that cycle, like clocks and days of the week. We write:

$$a \equiv b \pmod{n}$$

This means $a$ is **congruent to** $b$ **modulo** $n$, meaning they leave the same remainder when divided by $n$, or equivalently, $n \mid (a - b)$. For example, $15 \equiv 3 \pmod{12}$.

Congruence is an **equivalence relation** partitioning integers into $n$ **residue classes** for remainders $0, 1, \dots, n-1$. 

| Property | Meaning |
| --- | --- |
| Addition | $a+c \equiv b+d$ |
| Multiplication | $a \cdot c \equiv b \cdot d$ |

Because congruence is compatible with arithmetic, you can **reduce as you go**. To find $17 \cdot 17 \bmod 5$, use $17 \equiv 2$ to get $2 \cdot 2 = 4 \pmod 5$, avoiding 289.

## The Division Exception

**Division is the exception** in modular arithmetic. You cannot freely divide congruences or cancel common factors as you do in standard algebra.

| Operation | Allowed? | Rule |
| --- | --- | --- |
| Add / Sub / Mul | Yes | Substitute freely |
| Division | **No** | Requires inverse |

**Common pitfall:** Cancelling common factors blindly. For example, $6 \equiv 2 \pmod 4$, but cancelling 2 gives the false statement $3 \equiv 1 \pmod 4$.

Valid **division** mod $n$ relies entirely on **multiplicative inverses**, which only exist for numbers **coprime** to $n$.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Select every operation you may perform on congruences modulo n with no extra conditions.

A. Replace any number by its remainder mod n at any stage
B. Subtract two congruences
C. Multiply two congruences
D. Cancel a common factor from both sides
E. Add two congruences

**Answer:** A. Replace any number by its remainder mod n at any stage; B. Subtract two congruences; C. Multiply two congruences; E. Add two congruences

**Why:** Addition, subtraction, multiplication and reduce-as-you-go are all safe. Cancellation is not: 6 is congruent to 2 mod 4, but cancelling 2 gives '3 congruent to 1 mod 4', which is false. Division mod n needs a multiplicative inverse, and those exist only for numbers coprime to n.

Page: https://tryals.app/practice/mathematics-i/modular-arithmetic/select-every-operation-you-may-perform-on-congruences-modulo-n-with

### 2. A congruence may be divided through by a factor only when that factor is coprime to the modulus.

**Answer:** True

**Why:** True. $6 \equiv 2 \pmod 4$ divided by 2 gives the false $3 \equiv 1 \pmod 4$, because 2 shares a factor with the modulus. Where the factor is coprime the division is valid; otherwise the modulus must be divided too, giving $3 \equiv 1 \pmod 2$.

Page: https://tryals.app/practice/mathematics-i/modular-arithmetic/a-congruence-may-be-divided-through-by-a-factor-only-when-that-factor

### 3. Find the last digit of 7 raised to the power 4. (The last digit of a number is that number mod 10.)

**Answer:** 1

**Why:** 7 squared = 49 = 9 mod 10, and 9 squared = 81 = 1 mod 10, so the last digit is 1. (Indeed 7 to the fourth is 2401.) Reducing at every stage keeps the numbers to one digit, the technique that makes modular exponentiation practical even for the huge exponents used in cryptography.

Page: https://tryals.app/practice/mathematics-i/modular-arithmetic/find-the-last-digit-of-7-raised-to-the-power-4-the-last-digit-of-a

### 4. Congruence mod n is an equivalence relation, so it partitions the integers into n residue classes. Why does that structure make it legitimate to add and multiply classes rather than individual numbers?

A. Because the smallest member of each class is used by convention, which removes the ambiguity.
B. Because residue classes are numbers themselves, so the ordinary rules of arithmetic apply directly.
C. Because addition and multiplication happen to work, though no general reason guarantees it.
D. Because the result does not depend on which representative you pick.

**Answer:** D. Because the result does not depend on which representative you pick.

**Why:** The question is whether the answer depends on which representative you picked, and it does not: 3 + 5 ≡ 1 and 10 + 12 ≡ 1 mod 7. That is what turns the residue classes into an arithmetic system in their own right. Not every operation survives, reducing the *exponent* mod n is not well defined, since 2¹ = 2 and 2⁸ ≡ 4 mod 7.

Page: https://tryals.app/practice/mathematics-i/modular-arithmetic/congruence-mod-n-is-an-equivalence-relation-so-it-partitions-the

### 5. Congruence mod 4 splits the integers into four residue classes. Sort each number into its class.

**Answer:**

- Remainder 0: 12, 100
- Remainder 1: 17
- Remainder 2: 26
- Remainder 3: 31, -1

**Why:** 12 and 100 are multiples of 4; 17 = 4(4) + 1; 26 = 4(6) + 2; 31 = 4(7) + 3; and -1 = 4(-1) + 3. There are exactly 4 classes, and every integer, negative ones included, lands in one of them. That partition is what makes congruence an equivalence relation.

Page: https://tryals.app/practice/mathematics-i/modular-arithmetic/congruence-mod-4-splits-the-integers-into-four-residue-classes-sort

### 6. The ISBN check digit is chosen so a weighted sum of the digits is divisible by 11. Why does that catch a transposed pair, which a simple sum would miss?

A. Because 11 is prime, and prime moduli detect all errors
B. Because transposition changes the number of digits, which is checked separately
C. Because the check digit is recomputed from scratch on every scan
D. Because each position carries a different weight

**Answer:** D. Because each position carries a different weight

**Why:** A plain sum is order-blind, so the commonest human error, swapping adjacent digits, sails through. Position-dependent weights make order part of the total, and the same idea runs bank account validation, barcodes and every error-detecting code in use.

Page: https://tryals.app/practice/mathematics-i/modular-arithmetic/the-isbn-check-digit-is-chosen-so-a-weighted-sum-of-the-digits-is