DM-07

Course 7

Number Theory

Explore the properties of integers: divisibility, prime numbers, and modular arithmetic. These concepts form the foundation of cryptography and computer security.

Learning Objectives

Understand divisibility and its properties
Perform modular arithmetic operations
Apply the Euclidean algorithm to find GCD
Understand prime numbers and factorization
Find modular multiplicative inverses
Apply Bézout's identity

1. Divisibility

Definition 7.1: Divisibility

Let $a$ and $b$ be integers with $a \neq 0$ . We say $a$ divides $b$ , written $a \mid b$ , if there exists an integer $k$ such that $b = ak$ .

We also say $a$ is a factor or divisor of $b$ , and $b$ is a multiple of $a$ .

Theorem 7.1: Properties of Divisibility

Let $a, b, c$ be integers:

If $a \mid b$ and $a \mid c$ , then $a \mid (b + c)$
If $a \mid b$ , then $a \mid bc$ for any integer $c$
If $a \mid b$ and $b \mid c$ , then $a \mid c$ (transitivity)

Theorem 7.2: Division Algorithm

For any integers $a$ and $d > 0$ , there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

a = dq + r \quad \text{where } 0 \leq r < d

2. Modular Arithmetic

Definition 7.2: Congruence

Let $n$ be a positive integer. We say $a$ is congruent to $b$ modulo $n$ , written $a \equiv b \pmod{n}$ , if $n \mid (a - b)$ .

Equivalently, $a$ and $b$ have the same remainder when divided by $n$ .

Theorem 7.3: Properties of Congruence

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$ , then:

$a + c \equiv b + d \pmod{n}$
$a - c \equiv b - d \pmod{n}$
$ac \equiv bd \pmod{n}$
$a^k \equiv b^k \pmod{n}$ for any positive integer $k$

Example: Modular Arithmetic

Calculate: $7^{100} \mod 10$

Solution: Find the pattern of powers of 7 mod 10:

$7^1 \equiv 7 \pmod{10}$
$7^2 \equiv 49 \equiv 9 \pmod{10}$
$7^3 \equiv 63 \equiv 3 \pmod{10}$
$7^4 \equiv 21 \equiv 1 \pmod{10}$

The cycle repeats every 4. Since $100 = 4 \times 25$ :

$7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{10}$

3. GCD and Euclidean Algorithm

Definition 7.3: Greatest Common Divisor

The greatest common divisor of integers $a$ and $b$ , denoted $\gcd(a, b)$ , is the largest positive integer that divides both $a$ and $b$ .

If $\gcd(a, b) = 1$ , we say $a$ and $b$ are coprime (relatively prime).

Algorithm 7.1: Euclidean Algorithm

To find $\gcd(a, b)$ where $a \geq b > 0$ :

Euclidean(a, b):

while b ≠ 0:

r = a mod b

a = b

b = r

return a

Correctness: Based on the fact that $\gcd(a, b) = \gcd(b, a \mod b)$

Example: Euclidean Algorithm

Find: $\gcd(252, 105)$

$252 = 2 \times 105 + 42$

$105 = 2 \times 42 + 21$

$42 = 2 \times 21 + 0$

Therefore, $\gcd(252, 105) = 21$

Theorem 7.4: Bézout's Identity

For any integers $a$ and $b$ with $d = \gcd(a, b)$ , there exist integers $x$ and $y$ such that:

ax + by = d

These coefficients can be found using the Extended Euclidean Algorithm.

4. Prime Numbers

Definition 7.4: Prime Number

An integer $p > 1$ is prime if its only positive divisors are 1 and $p$ .

An integer $> 1$ that is not prime is called composite.

Theorem 7.5: Fundamental Theorem of Arithmetic

Every integer $> 1$ can be expressed as a product of primes uniquely, up to the order of factors.

Theorem 7.6: Infinitude of Primes

There are infinitely many prime numbers.

Proof of Infinitely many primes (Euclid)

Suppose there are finitely many primes: $p_1, p_2, \ldots, p_n$ .

Consider $N = p_1 p_2 \cdots p_n + 1$ .

N is not divisible by any $p_i$ (remainder is 1).

So either N is prime, or N has a prime factor not in our list.

Both cases contradict our assumption. ∎

∎

5. Modular Multiplicative Inverse

Definition 7.5: Multiplicative Inverse

The multiplicative inverse of $a$ modulo $n$ is an integer $x$ such that:

ax \equiv 1 \pmod{n}

We write $x = a^{-1} \pmod{n}$ .

Theorem 7.7: Existence of Inverse

$a$ has a multiplicative inverse modulo $n$ if and only if $\gcd(a, n) = 1$ .

Example: Finding Modular Inverse

Find: $7^{-1} \pmod{11}$

We need $x$ such that $7x \equiv 1 \pmod{11}$ .

Using Extended Euclidean Algorithm or testing:

$7 \times 8 = 56 = 5 \times 11 + 1 \equiv 1 \pmod{11}$

Therefore, $7^{-1} \equiv 8 \pmod{11}$

Practice Quiz

Number Theory Quiz

Questions

Correct

Accuracy

What is

17 \mod 5

Easy

Not attempted

What is

\gcd(48, 18)

Easy

Not attempted

a \equiv 3 \pmod{7}

and

b \equiv 5 \pmod{7}

, what is

a + b \pmod{7}

Medium

Not attempted

Which statement about primes is TRUE?

Easy

Not attempted

What is the multiplicative inverse of 3 modulo 7?

Medium

Not attempted

a \mid b

and

a \mid c

implies:

Medium

Not attempted

The Fundamental Theorem of Arithmetic states that:

Medium

Not attempted

Bézout's identity states that for

\gcd(a, b) = d

Hard

Not attempted

Two integers are coprime if:

Easy

Not attempted

\gcd(a, n) = 1

, then

a

has a multiplicative inverse modulo

n

Hard

Not attempted

Frequently Asked Questions

Why is number theory important in computer science?

Number theory is the foundation of:

Cryptography: RSA, Diffie-Hellman rely on modular arithmetic and primes
Hash functions: Often use modular arithmetic
Random number generation: Based on number-theoretic properties
Error-correcting codes: Use finite field arithmetic

How do I quickly find GCD?

Use the Euclidean algorithm:

Divide larger by smaller, get remainder
Replace larger with smaller, smaller with remainder
Repeat until remainder is 0
GCD is the last non-zero remainder

What's the difference between mod and remainder?

In mathematics, $a \mod n$ is always in range $[0, n-1]$ .

Some programming languages may return negative values for negative dividends. Mathematical modulo is always non-negative.

When does a modular inverse exist?

$a^{-1} \pmod{n}$ exists if and only if $\gcd(a, n) = 1$ (a and n are coprime).

If n is prime, every non-zero element has an inverse (this makes $\mathbb{Z}_p$ a field).

How is the Fundamental Theorem of Arithmetic used?

The unique prime factorization is used to:

Find GCD and LCM from prime factorizations
Count divisors of a number
Solve Diophantine equations
Prove theorems about integers