Modular Math and Number Theory: RSA Groundwork

In this page, we're introducing the concept of modular math and other necessary number theory concepts

GCD

What is a GCD?

• GCD stands for Greatest Common Divisor. It’s the largest number that divides two (or more) numbers without leaving a remainder.

• In simpler terms, it’s the biggest number that two numbers share as a factor.

Why is the GCD Useful?

• Simplifying Fractions: To reduce fractions to their simplest form, you divide both the numerator and the denominator by their GCD.

• Problem Solving: In math and programming, the GCD helps solve problems involving ratios, dividing items evenly, and more.

How to Find the GCD

Method 1: Listing Factors

1. List all factors of each number.

2. Identify the common factors.

3. The largest common factor is the GCD.

Example: Find the GCD of 12 and 18.

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

• Factors of 18: 1, 2, 3, 6, 9, 18

• Common factors: 1, 2, 3, 6

• GCD = 6 (the largest common factor)

Method 2: Using Prime Factorization

1. Break each number down into its prime factors.

2. Identify the common prime factors and multiply them to get the GCD.

Example: Find the GCD of 36 and 48.

• Prime factors of 36: 2×2×3×3

• Prime factors of 48: 2×2×2×2×3

• Common prime factors: 2×2×3=12

• GCD = 12

Method 3: Using the Euclidean Algorithm

• The Euclidean algorithm is an efficient way to find the GCD of two large numbers.

• Steps:

  1. Divide the larger number by the smaller number and find the remainder.

  2. Replace the larger number with the smaller number, and the smaller number with the remainder.

  3. Repeat this until the remainder is 0. The last non-zero remainder is the GCD.

Example: Find the GCD of 48 and 18.

• Step 1: 48÷18=2 with remainder 12

• Step 2: Replace 48 with 18, and 18 with 12.

• Step 3: 18÷12=1 with remainder 6

• Step 4: Replace 18 with 12, and 12 with 6.

• Step 5: 12÷6=2 with remainder 0

• GCD = 6 (last non-zero remainder)

Key Points to Remember

• GCD of 1: If the GCD of two numbers is 1, they are called coprime or relatively prime (meaning they don’t share any factors except 1).

• GCD of a Number with Itself: The GCD of any number with itself is the number itself (e.g., GCD of 7 and 7 is 7).

• Zero Case: The GCD of any number and 0 is the number itself (e.g., GCD of 5 and 0 is 5).

Practical Applications

• Simplifying Fractions: You can simplify 18/24 by dividing both the numerator and denominator by their GCD, which is 6. 24÷6=4 18÷6=3.

$\frac{18}{24}$

$\frac{18 \div 6}{24 \div 6} = \frac{3}{4}$

• Programming: The GCD is used in algorithms and cryptography (such as RSA encryption) and can be calculated in many programming languages using built-in functions.

Modular Math

Introduction

When we divide two integers we will have an equation that looks like the following:

$\dfrac{A}{B} = Q \text{ remainder } R$

A is the dividend

B is the divisor

Q is the quotient

R is the remainder

Sometimes, we are only interested in what the remainder is when we divide A by B.

For these cases there is an operator called the modulo operator (abbreviated as mod).

Using the same

$A , B , Q , \text{and } R, \text{ as above, we would have: } A \mod B = R$

We would say this as A modulo B is equal to R. Where B is referred to as the modulus.

For example:

$\frac{13}{5} = 2 \text{ remainder } 3 \newline 13 \text{ mod } 5 = 3$

Observe what happens when we increment numbers by one and then divide them by 3.

$\begin{array}{rcl} \frac{0}{3} &=& 0 \text{ remainder } \mathbf{0} \\ \newline \frac{1}{3} &=& 0 \text{ remainder } \mathbf{1} \\ \newline \frac{2}{3} &=& 0 \text{ \newline remainder } \mathbf{2} \\ \newline \frac{3}{3} &=& 1 \text{ remainder } \mathbf{0} \\ \newline \frac{4}{3} &=& 1 \text{ remainder } \mathbf{1} \\ \newline \frac{5}{3} &=& 1 \text{ remainder } \mathbf{2} \\ \newline\frac{6}{3} &=& 2 \text{ remainder } \mathbf{0} \end{array}$

The remainders start at 0 and increases by 1 each time, until the number reaches one less than the number we are dividing by. After that, the sequence repeats.

By noticing this, we can visualize the modulo operator by using circles.

We write 0 at the top of a circle and continuing clockwise writing integers 1, 2, ... up to one less than the modulus.

For example, a clock with the 12 replaced by a 0 would be the circle for a modulus of 12.

To find the result of A mod B we can follow these steps:

1. Construct this clock for size B

2. Start at 0 and move around the clock A steps

3. Wherever we land is our solution.

(If the number is positive we step clockwise, if it's negative we step counter-clockwise.)

Example:

A)

$8 \text{ mod } 4 = ?$

With a modulus of 4 we make a clock with numbers 0, 1, 2, 3.We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2, 3, 0.

We ended up at 0 so $8 \text{ mod } 4 = 0$ .

B)

$7 \text{ mod } 2 = ?$

With a modulus of 2 we make a clock with numbers 0, 1.

We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1.

We ended up at 0 so $7 \text{ mod } 2 = 1$ .

C)

$-5 \text{ mod } 3 = ?$

With a modulus of 3 we make a clock with numbers 0, 1, 2.We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative) 2, 1, 0, 2, 1.

We ended up at 1 so $-5 \text{ mod } 3 = 1$ .

SO:

If we have $A \text{ mod } B$ and we increase A by a multiple of B, we will end up in the same spot, i.e.

$A \text{ mod } B = (A + K \cdot B) \text{ mod } B$

For example:

$3 \text{ mod } 10 = 3 \\ 13 \text{ mod } 10 = 3 \\ 23 \text{ mod } 10 = 3 \\ 33 \text{ mod } 10 = 3 \\$

Congruence

You may see an expression like:

$A \equiv B \pmod C$ This says that A is congruent to B modulo C. It is similar to the expressions we used here, but not quite the same.

Let us discuss the meaning of congruence modulo by performing a thought experiment with the regular modulo operator.

Let's imagine we were calculating mod 5 for all of the integers:

Suppose we labelled 5 slices 0, 1, 2, 3, 4. Then, for each of the integers, we put it into a slice that matched the value of the integer mod 5.

Think of these slices as buckets, which hold a set of numbers. For example, 26 would go in the slice labelled 1, because $26 \text{ mod } 5 = 1$.

Above is a figure that shows some integers that we would find in each of the slices.

It would be useful to have a way of expressing that numbers belonged in the same slice. (Notice 26 is in the same slice as 1, 6, 11, 16, 21 in above example).

A common way of expressing that two values are in the same slice, is to say they are in the same equivalence class.

The way we express this mathematically for mod C is: $A \equiv B \ (\text{mod } C)$

The above expression is pronounced A is congruent to B modulo C.

Examining the expression closer:

1. $\equiv$ is the symbol for congruence, which means the values A and B are in the same equivalence class.

2. $(\text{mod } C)$ tells us what operation we applied to A and B.

3. When we have both of these, we call “$\equiv$” congruence modulo C.

e.g. $26 \equiv 11\ (\text{mod }5)$

$26 \text{ mod } 5 = 1$ so it is in the equivalence class for 1

$11 \text{ mod } 5 = 1$ so it is in the equivalence class for 1, as well.

Modular Arithmetic Properties

Let's explore the addition property of modular arithmetic:

(A + B) mod C = (A mod C + B mod C) mod C

Example:

Let A=14, B=17, C=5

Let's verify: (A + B) mod C = (A mod C + B mod C) mod C

LHS = Left Hand Side of the Equation

RHS = Right Hand Side of the Equation

LHS = (A + B) mod C

LHS = (14 + 17) mod 5

LHS = 31 mod 5LHS = 1

RHS = (A mod C + B mod C) mod C

RHS = (14 mod 5 + 17 mod 5) mod 5

RHS = (4 + 2) mod 5

RHS = 1

LHS = RHS = 1

Observe the figure below. If we want to calculate 12+9 mod 7 we can easily go around the modular circle for a sequence of 12+9 steps clockwise (as shown in the bottom left circle).

We can take a shortcut by observing that every 7 steps we end up in the same position on the modular circle. These complete loops around the modular circle don’t contribute to our final position. We ignore these complete loops around the circle by calculating each number mod 7 (as shown in the two upper modular circles). This will give us the number of clockwise steps, relative to 0, that contributed to each of their final positions around the modular circle.

Now, we only have to go around the circle clockwise the total of the number of steps that contributed to each of numbers final position (as shown in the bottom right modular circle). This method applies, in general, to any two integers and any modular circle.

Proposition. Let m ≥ 1 be an integer. Let a be an integer.

Then $a · b ≡ 1 \pmod m$ for some integer b if and only if $\gcd(a, m)=1$

Further, if $a · b1 ≡ a · b2 ≡ 1 \pmod m$, then $b1 ≡ b2 \pmod m$. We call b the (multiplicative) inverse of a modulo m

• Congruence Reflexive Property:

  $a \equiv a \pmod{m}$

  Any integer is congruent to itself modulo mmm.

• Congruence Symmetric Property:

  If $a \equiv b \pmod{m}$, then $b \equiv a \pmod{m}$.

• Congruence Transitive Property:

  If $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$, then $a \equiv c \pmod{m}$.

• Addition:

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

  $(a + c) \equiv (b + d) \pmod{m}$.

• Multiplication:

  If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $(a \times c) \equiv (b \times d) \pmod{m}$.

• Distributive Property:

  $a \times (b + c) \equiv (a \times b + a \times c) \pmod{m}$.

• Exponentiation:

  a^k \equiv b^k \pmod{m}$ if $a \equiv b \pmod{m}.

• Division (if m and b are coprime):

  If $a \equiv b \pmod{m}$ and $\gcd(b, m) = 1$, then $a \div b \equiv b^{-1} \pmod{m}$, where $b^{-1}$ is the modular inverse of $b$.

Credits to: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic For their great style in presenting modular arithmetic. Feel free to read their material for more!

Fermat Little Theorem (FLM):

let p be a prime number, a be a positive integer

then $a^p \equiv a \pmod p$

Example:

a = 2 , p = 7

$2^7 \mod 7 = 2$

Another form of FLM:

let p be a prime number, a be a positive integer

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

Euler’s Totient Function:

$\phi(n) = \text {the number of positive integers smaller than n and relatively prime to n}$

We have 3 cases

1. n is prime: phi(n) = n - 1

2. n is a product of 2 primes (p and q): phi(n) = (p-1)(q-1)

3. n is a squared prime: phi(n) = p*(p-1)

There’s a 4th case but you look it up ;)

Euler’s Theorem:

let p and q be distinct primes and n = p*q

and a is relatively prime to n, then

$$a^{\phi (n)} \equiv 1 \pmod n \text { which is similar to } \newline a^{(p-1)\times(q-1)} \mod n$$

The Chinese Remainder Theorem (CRT)

Suppose we wish to solve

𝑥 ≡ 2(mod 5)

𝑥 ≡ 3(mod 7)

for 𝑥. If we have a solution 𝑦, then 𝑦 + 35 is also a solution. So we only need to look for solutions modulo 35. By brute force, we find the only solution is 𝑥 ≡ 17(mod 35).

For any system of equations like this, the Chinese Remainder Theorem tells us there is always a unique solution up to a certain modulus, and describes how to find the solution efficiently.

Given pairwise coprime positive integers 𝑛1,𝑛2,…,𝑛𝑘 and arbitrary integers 𝑎1,𝑎2,…,𝑎𝑘 the system of simultaneous congruences

𝑥 ≡ 𝑎1(mod 𝑛1)

𝑥 ≡ 𝑎2(mod 𝑛2)

𝑥 ≡ 𝑎𝑘(mod 𝑛𝑘)

has a solution, and the solution is unique modulo 𝑁=𝑛1𝑛2⋯𝑛𝑘.