# Number Theory in Action

Mathematics I · Arithmetic and Number Theory · https://tryals.app/learn/mathematics-i/number-theory-in-action

## Pure Math to Security

Number theory was long prized as the purest mathematics, studied for its beauty. Today, those same abstract tools secure nearly every online transaction.

**Error detection and correction**. Check digits use modular arithmetic to catch mistakes. An ISBN's last digit makes a weighted sum $\equiv 0 \pmod{11}$, so a wrong digit breaks the congruence. **Error-correcting codes** extend this to repair corrupted data.

**Hashing**. A **hash function** maps keys to a fixed range, typically via reduction modulo a prime. This spreads values evenly for near-instant hash table lookups.

## Public-Key Cryptography

RSA public-key cryptography rests entirely on number theory, relying on two large **primes** whose product is public but whose factors are secret.

| Concept | Role in RSA |
| --- | --- |
| **Modular exponentiation** | Fast to compute for encryption/decryption |
| **Factoring difficulty** | Security rests on the fact that multiplying primes is easy, but factoring their product is hard |
| **Euler's theorems** | Guarantee that decryption correctly undoes encryption |

**Common pitfall**: Thinking security comes from a _secret algorithm_. RSA's method is completely public; the secret is the **prime factors**, not the procedure.

## Practice questions

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

### 1. The infinite geometric series 1 + 1/2 + 1/4 + 1/8 + … has infinitely many positive terms and sums to exactly 2. Why does adding infinitely many positive numbers not necessarily give an infinite total?

A. Because the terms eventually become zero, so only finitely many are actually added.
B. Because the series is finite in practice, since terms below a certain size are negligible.
C. Because the sum is the limit of partial sums, here approaching 2.
D. Because infinitely many additions cannot be performed, so the value 2 is an approximation rather than the exact sum.

**Answer:** C. Because the sum is the limit of partial sums, here approaching 2.

**Why:** An infinite sum is a definition rather than an infinitely long computation: the limit of 1, 1.5, 1.75, 1.875, each halving the remaining distance and never overshooting. So 2 is exact. What decides it is how fast terms shrink, and going to zero is not enough, the harmonic series does that and diverges. It is also the resolution of Zeno's paradox.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/the-infinite-geometric-series-1-1-2-1-4-1-8-has-infinitely

### 2. Order the stages of the RSA idea.

**Answer:**

1. Choose two large secret primes p and q
2. Publish their product n while keeping p and q secret
3. Encrypt a message by modular exponentiation mod n
4. Decrypt using an exponent derived from p and q
5. Security holds because factoring n back into p and q is infeasible

**Why:** Primes first, then the public product, then encryption, then decryption using the private information, and finally the security argument. Every stage uses a tool from this unit: primes, modular exponentiation, inverses (via Fermat and Euler), and the hardness of factoring.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/order-the-stages-of-the-rsa-idea

### 3. An ISBN-10 has digits d1 through d10 and must satisfy: 1 x d1 + 2 x d2 + ... + 10 x d10 is congruent to 0 mod 11. The first nine digits are 0, 3, 0, 6, 4, 0, 6, 1, 5. Find the check digit d10.

**Answer:** 2

**Why:** The weighted sum of the first nine digits is 6 + 24 + 20 + 42 + 8 + 45 = 145, which is 2 mod 11. Since the tenth weight 10 is congruent to -1, we need 2 - d10 congruent to 0, so d10 = 2. (This is the real ISBN 0-306-40615-2.) Changing any single digit breaks the congruence, which is exactly how the check catches errors.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/an-isbn-10-has-digits-d1-through-d10-and-must-satisfy-1-x-d1-2-x

### 4. A hash table has 13 slots and uses the hash function 'key mod 13'. Which slot does the key 1000 land in?

**Answer:** 12

**Why:** 1000 = 13(76) + 12, so the key lands in slot 12. Hash tables are pure 'reduce mod n': the table size is often chosen PRIME so that keys sharing a common factor with the size do not pile into the same few slots.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/a-hash-table-has-13-slots-and-uses-the-hash-function-key-mod-13

### 5. Sort each application by the number-theoretic idea it chiefly rests on.

**Answer:**

- Reduction modulo n: Assigning a key to a hash table slot, Computing an ISBN check digit
- Primes and factoring: Generating an RSA key pair
- The gcd: Reducing a fraction to lowest terms

**Why:** Hashing and check digits are pure remainder arithmetic. RSA lives on primes and the difficulty of factoring. Lowest terms and invertibility mod n are both gcd questions, a has an inverse exactly when gcd(a, n) = 1. Six different-looking tasks, three underlying ideas.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/sort-each-application-by-the-number-theoretic-idea-it-chiefly-rests

### 6. Complete the source of RSA's security.

**Answer:** RSA is secure because **factoring a large product of two primes is computationally hard**.

**Why:** Security comes from a hard mathematical problem, not concealment. Modular exponentiation must be EASY, it is how encryption works, while its inverse, factoring, must be hard. Small primes would be factored instantly, which is why real keys use enormous ones.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/complete-the-source-of-rsas-security

### 7. Select every idea from this unit that RSA depends on.

A. Primes
B. Factoring being computationally hard
C. Modular exponentiation
D. The triangle inequality
E. Coprimality and multiplicative inverses

**Answer:** A. Primes; B. Factoring being computationally hard; C. Modular exponentiation; E. Coprimality and multiplicative inverses

**Why:** Primes build the key, modular exponentiation performs the encryption, coprimality and inverses make the decryption exponent work, and the hardness of factoring supplies the security. The triangle inequality is a fact about absolute value on the real line and plays no part here.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/select-every-idea-from-this-unit-that-rsa-depends-on

### 8. Zeno argued you can never cross a room: first half the distance, then half the rest, forever. Why does the mathematics of series dissolve the paradox?

A. Because the distances eventually become zero, ending the sequence
B. Because space is discrete, so there is a smallest step
C. Because the times form a convergent series with a finite total
D. Because motion is continuous and cannot be divided into steps at all

**Answer:** C. Because the times form a convergent series with a finite total

**Why:** The steps shrink fast enough that the times sum to a finite number: infinitely many additions with a finite total. Zeno's error was assuming an infinite count of intervals means infinite duration, and the resolution had to wait about two thousand years for the definition of a convergent series.

Page: https://tryals.app/practice/mathematics-i/number-theory-in-action/zeno-argued-you-can-never-cross-a-room-first-half-the-distance-then