Number Theory Basics: Primes, Divisibility and Modular Arithmetic

Number theory is the study of whole numbers and the patterns hidden inside them. It sounds simple, but the same ideas power online banking, cryptography and error-detecting codes. This guide walks you through primes, divisibility, the greatest common divisor and modular arithmetic, with worked examples you can follow line by line.

Divisibility: The Starting Point

We say an integer \( a \) divides an integer \( b \), written \( a \mid b \), if there is an integer \( k \) with \( b = ak \). For example, \( 6 \mid 42 \) because \( 42 = 6 \times 7 \), but \( 5 \nmid 42 \).

A few properties you will use constantly:

• If \( a \mid b \) and \( b \mid c \), then \( a \mid c \).
• If \( a \mid b \) and \( a \mid c \), then \( a \mid (mb + nc) \) for any integers \( m, n \).
• If \( a \mid b \) and \( b \neq 0 \), then \( |a| \le |b| \).

The Division Algorithm

For any integers \( a \) and \( b > 0 \), there are unique integers \( q \) (quotient) and \( r \) (remainder) such that

$$ a = bq + r, \qquad 0 \le r < b. $$

For instance, dividing 100 by 7 gives \( 100 = 7 \times 14 + 2 \), so \( q = 14 \) and \( r = 2 \). Almost everything else in this article grows out of this one statement.

Prime Numbers

A prime is an integer \( p > 1 \) whose only positive divisors are 1 and \( p \). The first few are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. A number greater than 1 that is not prime is composite.

The Fundamental Theorem of Arithmetic

Every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. For example:

$$ 360 = 2^3 \times 3^2 \times 5. $$

This factorisation tells you a lot. The number of positive divisors of \( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \) is \( (a_1 + 1)(a_2 + 1)\cdots(a_k + 1) \). So 360 has \( (3+1)(2+1)(1+1) = 24 \) divisors.

Testing Whether a Number Is Prime

To test \( n \), you only need to check divisibility by primes up to \( \sqrt{n} \). If \( n \) had a factor larger than \( \sqrt{n} \), it would also need a matching factor smaller than \( \sqrt{n} \). For \( n = 97 \), \( \sqrt{97} \approx 9.8 \), so check 2, 3, 5 and 7. None divides 97, so 97 is prime.

Greatest Common Divisor and the Euclidean Algorithm

The greatest common divisor \( \gcd(a, b) \) is the largest positive integer dividing both \( a \) and \( b \). The Euclidean algorithm finds it quickly using the fact that \( \gcd(a, b) = \gcd(b, r) \), where \( r \) is the remainder when \( a \) is divided by \( b \).

Worked Example 1: Find \( \gcd(252, 198) \) and Express It as a Combination

Step 1: Apply the division algorithm repeatedly.

$$ 252 = 1 \times 198 + 54 $$

$$ 198 = 3 \times 54 + 36 $$

$$ 54 = 1 \times 36 + 18 $$

$$ 36 = 2 \times 18 + 0 $$

The last non-zero remainder is 18, so \( \gcd(252, 198) = 18 \).

Step 2: Work backwards (the extended Euclidean algorithm). Bézout's identity says we can write \( 18 = 252x + 198y \) for some integers \( x, y \).

From the third line: \( 18 = 54 - 36 \).

From the second line: \( 36 = 198 - 3 \times 54 \). Substitute:

$$ 18 = 54 - (198 - 3 \times 54) = 4 \times 54 - 198. $$

From the first line: \( 54 = 252 - 198 \). Substitute:

$$ 18 = 4(252 - 198) - 198 = 4 \times 252 - 5 \times 198. $$

Step 3: Check. \( 4 \times 252 = 1008 \) and \( 5 \times 198 = 990 \), and \( 1008 - 990 = 18 \). Correct.

Two numbers are coprime when their gcd is 1. This idea is the key to dividing in modular arithmetic.

Modular Arithmetic

We write \( a \equiv b \pmod{n} \) when \( n \mid (a - b) \), meaning \( a \) and \( b \) leave the same remainder on division by \( n \). Think of a clock: \( 15 \equiv 3 \pmod{12} \), because 3 p.m. is 15:00.

Congruences behave nicely with addition and multiplication. If \( a \equiv b \) and \( c \equiv d \pmod{n} \), then

$$ a + c \equiv b + d \pmod{n}, \qquad ac \equiv bd \pmod{n}. $$

That lets you shrink huge numbers at every step instead of computing them in full.

Fermat's Little Theorem

If \( p \) is prime and \( p \nmid a \), then

$$ a^{p-1} \equiv 1 \pmod{p}. $$

Worked Example 2: Find the Remainder When \( 3^{100} \) Is Divided by 7

Step 1: 7 is prime and \( 7 \nmid 3 \), so Fermat gives \( 3^6 \equiv 1 \pmod{7} \).

Step 2: Divide the exponent by 6: \( 100 = 6 \times 16 + 4 \).

Step 3: Rewrite the power:

$$ 3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 3^4 \equiv 81 \pmod{7}. $$

Step 4: Reduce: \( 81 = 7 \times 11 + 4 \), so \( 81 \equiv 4 \pmod{7} \).

The remainder is 4.

Worked Example 3: Solve \( 7x \equiv 3 \pmod{26} \)

Step 1: Since \( \gcd(7, 26) = 1 \), 7 has an inverse modulo 26, a number \( m \) with \( 7m \equiv 1 \pmod{26} \).

Step 2: Find it. Testing multiples, \( 7 \times 15 = 105 = 4 \times 26 + 1 \), so \( 7^{-1} \equiv 15 \pmod{26} \). (You could also get this from the extended Euclidean algorithm.)

Step 3: Multiply both sides by 15:

$$ x \equiv 15 \times 3 = 45 \equiv 19 \pmod{26}. $$

Step 4: Check: \( 7 \times 19 = 133 = 5 \times 26 + 3 \). So \( 133 \equiv 3 \pmod{26} \). Correct.

Common Mistakes to Avoid

• Dividing a congruence freely. You can cancel a factor only if it is coprime to the modulus. From \( 2x \equiv 4 \pmod{6} \), you cannot conclude \( x \equiv 2 \pmod 6 \), because \( x = 5 \) also works.
• Forgetting that 1 is not prime. Uniqueness of factorisation would fail if it were.
• Skipping the check. Substituting your answer back takes seconds and catches most arithmetic slips.

Where Number Theory Shows Up

• Cryptography: RSA encryption relies on how hard it is to factor large numbers and on modular exponentiation.
• Check digits: ISBNs and bank card numbers use modular arithmetic to detect typing errors.
• Computer science: hashing, random number generators and cyclic schedules all use remainders.

Key Takeaways

• \( a \mid b \) means \( b = ak \) for some integer \( k \); the division algorithm \( a = bq + r \) underpins everything else.
• Every integer above 1 has a unique prime factorisation, which also counts its divisors.
• The Euclidean algorithm finds the gcd quickly, and running it backwards writes the gcd as \( ax + by \).
• Modular arithmetic lets you reduce at every step; Fermat's Little Theorem makes large powers manageable.
• Always check solutions of congruences by substituting back.

If a number theory problem set has you stuck, Amathify's subject experts and PhD scholars can send you clear, step-by-step solutions. Message us on WhatsApp or use the "Ask a Question" form to get help with your assignment.