Coprime Numbers

Dividing Evenly

Some divisions come out clean:

$12 \div 3 = 4$

No remainder. We say 3 divides 12 evenly.

Some don’t:

$12 \div 5 = 2 \text{ remainder } 2$

5 does not divide 12 evenly.

Factors

A factor of a number is anything that divides it evenly.

What are the factors of 12?

• $12 \div 1 = 12$ ✓
• $12 \div 2 = 6$ ✓
• $12 \div 3 = 4$ ✓
• $12 \div 4 = 3$ ✓
• $12 \div 6 = 2$ ✓
• $12 \div 12 = 1$ ✓

Factors of 12: 1, 2, 3, 4, 6, 12

Common Factors

Sometimes two numbers share factors.

Factors of 8: 1, 2, 4, 8

Factors of 12: 1, 2, 3, 4, 6, 12

What do they have in common? 1, 2, and 4.

These are called common factors.

Coprime

Two numbers are coprime if their only common factor is 1.

Are 8 and 15 coprime?

Factors of 8: 1, 2, 4, 8

Factors of 15: 1, 3, 5, 15

Common factors: just 1.

8 and 15 are coprime.

Are 8 and 12 coprime?

Common factors: 1, 2, 4.

More than just 1.

8 and 12 are not coprime.

The Connection to Modular Inverse

Remember: the modular inverse of $a$ mod $n$ is a number $b$ where:

$(a \times b) \mod n = 1$

Here’s the key:

A modular inverse exists only if $a$ and $n$ are coprime.

If they share a factor, you can never reach 1. The inverse doesn’t exist.

If they’re coprime, you can always find an inverse.