# Primes and the Fundamental Theorem of Arithmetic

Mathematics I · Arithmetic and Number Theory · https://tryals.app/learn/mathematics-i/primes-and-the-fundamental-theorem-of-arithmetic

## The Atoms of the Integers

A **prime** is an integer greater than 1 whose only positive divisors are 1 and itself, like $2, 3, 5, 7, 11$. An integer greater than 1 that is not prime is **composite**. The number $1$ is **neither prime nor composite** because if 1 were prime, prime factorizations would lose their uniqueness.

The **Fundamental Theorem of Arithmetic** states that every integer greater than 1 can be written as a product of primes, and this factorization is **unique** up to factor order. For example, $60 = 2^2 \cdot 3 \cdot 5$. Primes act as the unique prime fingerprints and building blocks of all integers.

## Testing and Theory

Two core principles govern prime numbers:

| Principle | Rule / Method |
| --- | --- |
| **Infinity** | There are infinitely many primes (Euclid's theorem) |
| **Primality Test** | Check divisors only up to $\sqrt{n}$ |

For the primality test, if $n = ab$ with $a \le b$, then $a \le \sqrt{n}$. A factor below the square root must exist if the number is composite.

> **Common pitfall:** Thinking 1 is prime, or checking divisors all the way up to $n$. You only need to check up to $\sqrt{n}$.

## Practice questions

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

### 1. If 1 were counted as prime, unique factorisation would fail.

**Answer:** True

**Why:** True. $12 = 2^2 \cdot 3 = 1 \cdot 2^2 \cdot 3 = 1^{2} \cdot 2^{2} \cdot 3$, factorisations would stop being unique, and the Fundamental Theorem of Arithmetic would need an awkward exception. Excluding 1 is what keeps 'exactly one factorisation' true as stated.

Page: https://tryals.app/practice/mathematics-i/primes-and-the-fundamental-theorem-of-arithmetic/if-1-were-counted-as-prime-unique-factorisation-would-fail

### 2. Select every statement that the Fundamental Theorem of Arithmetic guarantees.

A. Every integer greater than 1 can be written as a product of primes
B. Since 60 = 2 x 2 x 3 x 5, no other collection of primes multiplies to 60
C. Two different integers greater than 1 can share an identical prime factorization
D. That prime factorization is unique apart from the order of the factors
E. 1 factors uniquely as a product of one prime

**Answer:** A. Every integer greater than 1 can be written as a product of primes; B. Since 60 = 2 x 2 x 3 x 5, no other collection of primes multiplies to 60; D. That prime factorization is unique apart from the order of the factors

**Why:** Existence plus uniqueness is the whole theorem, and the 60 statement is uniqueness applied. 1 is excluded because it is not greater than 1 and has no prime factors at all. And identical factorizations force identical products, so distinct integers can never share one.

Page: https://tryals.app/practice/mathematics-i/primes-and-the-fundamental-theorem-of-arithmetic/select-every-statement-that-the-fundamental-theorem-of-arithmetic

### 3. RSA encryption relies on multiplying two large primes being easy while factoring the product is hard. Why is that asymmetry the whole security model?

A. Because large primes are difficult to discover, limiting who can participate
B. Because the public key is the product and the private key the factors
C. Because factoring has been proved impossible for large numbers
D. Because multiplication and factoring produce different numbers

**Answer:** B. Because the public key is the product and the private key the factors

**Why:** The product is public and the factors are the secret, so a one-way gap becomes an asymmetry between sending and reading. Option 4 overstates it dangerously: factoring is not proved hard, merely not known to be easy, and Shor's algorithm factors efficiently on a quantum computer, which is why post-quantum cryptography exists.

Page: https://tryals.app/practice/mathematics-i/primes-and-the-fundamental-theorem-of-arithmetic/rsa-encryption-relies-on-multiplying-two-large-primes-being-easy

### 4. Order the steps of Euclid's proof that there are infinitely many primes.

**Answer:**

1. Assume for contradiction that the primes are just p1, p2, ..., pk
2. Form N by multiplying all of them together and adding 1
3. Observe that N leaves remainder 1 on division by each pi
4. So no pi divides N, yet N has some prime factor
5. That prime factor is missing from the list, contradicting the assumption

**Why:** Assume finiteness, build a number that dodges every listed prime, then note it still has SOME prime factor, which must therefore be new. The subtle point is that N need not itself be prime, it only needs a prime factor outside the list.

Page: https://tryals.app/practice/mathematics-i/primes-and-the-fundamental-theorem-of-arithmetic/order-the-steps-of-euclids-proof-that-there-are-infinitely-many

### 5. 1 is neither prime nor composite. Why is it excluded rather than counted as prime?

A. Because primality is defined only for integers greater than 2
B. Because 1 is a unit and units are excluded by historical convention
C. Because 1 has only one divisor rather than two
D. Because unique factorisation would fail, with 6 factorable many ways

**Answer:** D. Because unique factorisation would fail, with 6 factorable many ways

**Why:** The exclusion protects the theorem. Admitting 1 makes every factorisation non-unique, which is exactly the property the fundamental theorem of arithmetic asserts.

Page: https://tryals.app/practice/mathematics-i/primes-and-the-fundamental-theorem-of-arithmetic/1-is-neither-prime-nor-composite-why-is-it-excluded-rather-than