# Congruences and Applications

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

## Solving Congruences

Modular arithmetic powers check digits, hashing, calendars, and cryptography. A **linear congruence** has the form $ax \equiv b \pmod{n}$, solved for the unknown residue $x$.

The key tool is the **multiplicative inverse**: $a^{-1}$ is a residue satisfying $a \cdot a^{-1} \equiv 1 \pmod n$. Multiplying both sides by it yields $x \equiv a^{-1} b$.

**$a$ has an inverse mod $n$ if and only if $\gcd(a, n) = 1$** (coprime). Thus, $ax \equiv b \pmod n$ has a unique solution when coprime; otherwise it yields several or none.

| Modulus Case | $\gcd(a, n)$ Condition | Solution Outcome |
| --- | --- | --- |
| Coprime | $\gcd(a, n) = 1$ | Unique solution |
| Not Coprime | $\gcd(a, n) > 1$ | None or several |

**Common pitfall:** Never "divide by $a$" when $a$ and $n$ are not coprime. The inverse $a^{-1}$ only exists when $\gcd(a, n) = 1$.

## Theorems & Applications

Two celebrated theorems make modular computation easy and powerful:

- **Fermat's little theorem**: If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. This provides inverses via $a^{-1} \equiv a^{p-2}$ and enables fast primality tests.
- **The Chinese remainder theorem**: A system of congruences with coprime moduli has a unique solution modulo the product of moduli, reassembling a number from remainders.

**Applications** are everywhere:
- **Check digits**: ISBN and credit cards append a digit making a weighted sum $\equiv 0 \pmod n$ to catch errors.
- **Hash functions**: Reduce keys modulo a table size.
- **Public-key cryptography (RSA)**: Rests on modular exponentiation being easy while its inverse (factoring or discrete logarithm) is hard.

## Practice questions

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

### 1. Order the steps of solving 4x is congruent to 6 mod 7.

**Answer:**

1. Check gcd(4, 7) = 1, so a unique solution exists
2. Find the inverse of 4 mod 7: it is 2, since 4 x 2 = 8 = 1 mod 7
3. Multiply both sides by 2, giving x congruent to 2 x 6 = 12 mod 7
4. Reduce to get x congruent to 5 mod 7

**Why:** Coprimality first, then the inverse, then multiply, then reduce. Check the answer: 4 x 5 = 20 = 7(2) + 6. Skipping the coprimality check is what leads students to 'divide' in cases where no inverse exists at all.

Page: https://tryals.app/practice/mathematics-i/congruences-and-applications/order-the-steps-of-solving-4x-is-congruent-to-6-mod-7

### 2. The congruence 2x ≡ 3 (mod 4) has no solution, while 3x ≡ 3 (mod 4) has exactly one. Why does the coefficient decide whether solutions exist at all?

A. Because the equation 2x ≡ 3 is arithmetically false, whereas 3x ≡ 3 has the obvious solution x = 1.
B. Because 3 is prime and 2 is not, and only prime coefficients admit inverses.
C. Because ax ≡ b is solvable exactly when gcd(a, n) divides b.
D. Because 2 is even and 4 is even, and congruences require the coefficient and modulus to have opposite parity.

**Answer:** C. Because ax ≡ b is solvable exactly when gcd(a, n) divides b.

**Why:** Work out what 2x reaches mod 4: 0, 2, 0, 2, multiplying by 2 collapses four classes onto two, so 3 is out of range. Multiplying by 3 permutes them instead, hitting every target once. The rule: ax ≡ b is solvable exactly when gcd(a, n) divides b. And 2 is prime with no inverse mod 4, so what matters is coprimality to n, not primality.

Page: https://tryals.app/practice/mathematics-i/congruences-and-applications/the-congruence-2x-3-mod-4-has-no-solution-while-3x-3-mod-4

### 3. Fermat's little theorem says a^(p−1) ≡ 1 (mod p) for prime p. Why does that make it a fast **primality test** rather than only a curiosity?

A. Because it identifies primes with certainty in all cases
B. Because it cheaply proves a number is NOT prime, without finding a factor
C. Because it is faster than trial division only for small numbers
D. Because it computes the prime factors directly when the test fails

**Answer:** B. Because it cheaply proves a number is NOT prime, without finding a factor

**Why:** It is a one-way test: failure proves compositeness without exhibiting a factor, and passing is only evidence. Carmichael numbers pass for every a and are composite, which is why practical tests like Miller-Rabin repeat with random bases, and why RSA key generation can find 2048-bit primes in moments.

Page: https://tryals.app/practice/mathematics-i/congruences-and-applications/fermats-little-theorem-says-a-p-1-1-mod-p-for-prime-p-why

### 4. Select every statement that is TRUE.

A. a has an inverse mod n exactly when gcd(a, n) = 1
B. Every nonzero residue mod 8 has an inverse
C. Every nonzero residue mod 7 has an inverse
D. An ISBN check digit makes a weighted sum congruent to 0 mod 11
E. RSA is secure because its algorithm is kept secret

**Answer:** A. a has an inverse mod n exactly when gcd(a, n) = 1; C. Every nonzero residue mod 7 has an inverse; D. An ISBN check digit makes a weighted sum congruent to 0 mod 11

**Why:** 7 is prime so every nonzero residue is coprime to it and invertible. 8 is not: 2, 4 and 6 share the factor 2 with 8 and have no inverse (2x is always even, so never 1 mod 8). RSA's algorithm is completely public; its security rests on factoring being hard.

Page: https://tryals.app/practice/mathematics-i/congruences-and-applications/select-every-statement-that-is-true