The Fundamental Theorem of Arithmetic

Posted on July 31, 2013 by Dan Ma

This post discusses and proves the fundamental theorem of arithmetic.

Finding the prime factors of a large integer is no easy feat. For example, the ninth Fermat number $F_9=2^{2^9}+1$ has 155 digits and has the following three prime factors:

$a=\text{2,424,833}$

$b=\text{7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657}$

$\displaystyle \begin{aligned} c=&\text{ 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519} \\&\text{ 023,905,821,316,144,415,759,504,705,008,092,818,711,693,940,737} \end{aligned}$

These prime factors have 9 digits, 49 digits and 99 digits, respectively. They were published in 1993 after lengthy calculations involving approximately 700 workstations and a supercomputer using a number field sieve algorithm (see [1]). If the project were to be done today, it could certainly be done much faster and more efficiently with the current state of the art in supercomputing. However, the project will still be no trivial feat.

The following 617-digit integer is a product of two prime numbers and has yet to be factored by anyone (or any computer or any sets of computers). According RSA Laboratories, barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come. For more background about this large number, see see RSA challenge number and RSA factoring challenge.

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

Though the implementation of prime factorization may be difficult or even impossible for large numbers, the fundamental theorem of arithmetic guarantees that any positive integer can be expressed uniquely as a product of prime numbers. The fundamental theorem of arithmetic is an essential theorem in number theory. In this post, we present of proof of this fundamental theorem.

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

The theorem has two parts – the existence and the uniqueness of the prime factorization. The existence part is relatively easy. We first prove the existence part. We use Euclid’s lemma to prove the uniqueness part.

Lemma 1

Any integer $n>1$ has a prime divisor.

Proof

Let $n$ be an integer with $n>1$ . If $n$ is prime, then it has a prime divisor, namely $n$ . So assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$ .

Now consider the set $D$ of all positive integer divisors of $n$ . The set $D$ is nonempty since $h$ and $k$ belong to this set. The set $D$ is also a finite set since an integer can only have finitely many integer divisors. Every finite set of real numbers has a smallest element. Let $p$ be the least element of $D$ .

The $p$ must be a prime number. If not, $p$ would have a positive divisor $q$ that is smaller than $p$ . Then $q$ is also a positive divisor of $n$ , contradicting that $p$ is the least element of $D$ . $\blacksquare$

Lemma 2

Any integer $n>1$ is a product of prime numbers.

Proof

We prove by induction. The lemma is certainly true for $n=2$ . Suppose the lemma is true for all positive integers $k$ where $k<n$ .

If $n$ is prime, then we are done. Assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$ . By induction hypothesis, both $h$ and $k$ are product of prime numbers. We can conclude that $n$ is also a product of prime numbers. $\blacksquare$

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$ , then $p \ \lvert \ a$ or $p \ \lvert \ b$ .

Proof of Euclid’s Lemma is found in this post. As a corollary of Euclid’s Lemma, we have the following lemma.

Lemma 3

If $p$ is a prime number and $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$ , then $p \ \lvert \ a_i$ for some $i$ .

Proof

We prove by induction. The case for $n=2$ is the Euclid’s Lemma. Assume that the lemma is true for $n$ where $n \ge 2$ . Suppose that $p \ \lvert (a_1 \cdot a_2 \cdots a_n \cdot a_{n+1})$ . By Euclid’s lemma, we have $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$ or $p \ \lvert \ a_{n+1}$ . In the first case, the induction hypothesis tells us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n$ . In the second case $p \ \lvert \ a_{n+1}$ . The two cases together tell us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n+1$ .

Since the validity of the lemma for $n$ implies the validity of the lemma for $n+1$ and since the lemma is true for $n=2$ , we now know that the lemma is true for all integers $n>1$ . This establishes the lemma. $\blacksquare$

Fundamental Theorem of Arithmetic

Any interger $n>1$ can be expressed uniquely as a product of prime numbers.

Proof

Let $n$ be an integer with $n>1$ . The existence of the prime factors of $n$ is established by Lemma 2. We now show there is only one prime factorization for $n$ . We would like to point out that order of the prime factors is not important. For example, we consider $2 \times 2 \times 3 \times 11$ and $11 \times 3 \times 2 \times 2$ as the same factorization for the integer $132$ .

Suppose that $n=p_1 \cdot p_2 \cdots p_h$ and $n=q_1 \cdot q_2 \cdots q_k$ are prime factorizations of the integer $n$ . We show that each $p_i$ is identical to some $q_j$ and each $q_s$ is identical to some $p_t$ . This implies that the prime numbers $p_1,p_2,\cdots,p_h$ are simply a rearrangement of $q_1,q_2,\cdots,q_k$ such that the only difference for the two factorizations is in the order of the factors.

Note that $p_1 \cdot (p_2 \cdots p_h)=q_1 \cdot q_2 \cdots q_k$ . Thus $p_1$ divides $q_1 \cdot q_2 \cdots q_k$ , or we write $p_1 \ \lvert \ q_1 \cdot q_2 \cdots q_k$ . By Lemma 3, $p_1 \ \lvert \ q_j$ for some $j$ . Since they are prime, $p_1=q_j$ . Then cancel out $p_1$ on both side of the equation, we have

$p_2 \cdot (p_3 \cdots p_h)=q_1 \cdot q_2 \cdots q_{j-1} \cdot q_{j+1} \cdots q_k$

Note that $p_2$ divides the right-hand side of the above equation. By Lemma 3, $p_2 \ \lvert \ q_w$ for some $w$ . Continue in this same manner, we see that each $p$ is identical to some $q$ . Furthermore, $h \le k$ . Otherwise, there would be some $p_i$ left after we cancel out all the $q_j$ , leading to the situation that the product of several prime numbers is equal to one.

By interchanging $p$ with $q$ , the same argument will also show that each $q$ is identical to some $p$ . Furthermore, $k \le h$ . Thus we have $h=k$ and that the two factorizations are really just rearrangement of each other. $\blacksquare$

Comment

From the fundamental theorem of arithmetic, it follows that any positive integer greater than one can be expressed uniquely in the following way:

$p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_m^{e_m}$

where $m$ is a positive integer and each $e_i \ge 1$ . Such representation of an integer is called a prime-power decomposition. For example, $7056=2^4 \cdot 3^2 \cdot 7^2$ .

___________________________________________________________________________________________________________________

Reference

Lenstra, A. K., Lenstra, H. W., Manasse, M. S., Pollard, J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

Euclid’s Lemma

Posted on July 29, 2013 by Dan Ma

This post presents a proof of a lemma that is called Euclid’s lemma, which is one of the fundamental properties of prime numbers. Euclid’s lemma is the statement that if a prime number divides a product of two integers, it must divide one of the factors.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

We first state all the tools that we need. The notation $a \ \lvert \ b$ refers to the condition that $a$ divides $b$ . The notation $\text{GCD}(a,b)$ refers to the greatest common divisor (GCD) of $a$ and $b$ .

___________________________________________________________________________________________________________________

Extended Euclidean Algorithm

Let $a$ and $b$ be integers. Let $d$ be the greatest common divisor of $a$ and $b$ . Then there exist integers $x$ and $y$ such that $ax+by=d$ .

The extended Euclidean algorithm is discussed in this post.

___________________________________________________________________________________________________________________

Lemma 1

If $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$ , then $d \ \lvert \ b$ .

Proof of Lemma 1

Suppose that $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$ . According to the extended Euclidean algorithm, for some integers $x$ and $y$ , we have $ax+dy=1$ . Multiplying both sides by $b$ , we have:

$abx+dby=b$

Since $d$ divides each term in the left-hand side of this equation, $d \ \lvert \ b$ . $\blacksquare$

___________________________________________________________________________________________________________________

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$ , then $p \ \lvert \ a$ or $p \ \lvert \ b$ .

Proof

If $p \ \lvert \ a$ , then we are done. So assume $p \not \lvert \ a$ , which implies that $\text{GCD}(p,a)=1$ . If $\text{GCD}(p,a)>1$ , $\text{GCD}(p,a)=p$ , which implies that $p \ \lvert \ a$ . Note that the only positive divisors of $p$ are $1$ and $p$ . By Lemma 1, $p \ \lvert \ b$ . $\blacksquare$

Comment

We would like to point out that the assumption that $p$ is prime is essential in Euclid’s lemma. Note that $8 \ \lvert \ (4 \cdot 4)$ and $8 \not \lvert \ 4$ .

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

The Euclidean Algorithm

Posted on July 28, 2013 by Dan Ma

In this post, we discuss the Euclidean algorithm, which is an algorithm to find the greatest comment divisor of two integers. This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

Introduction

Computing the greatest common divisor of two integers is a topic that is taught in elementary school and is also an important tool that is of great interest in number theory. We begin with an example.

Let’s take a simple example of finding the greatest common divisor of 24 and 60. In a math class in elementary school, one motivation of finding the greatest common divisor of 24 and 60 is to reduce the fraction $\displaystyle \frac{24}{60}$ to its lowest terms. The first step is to factor each of the numerator and denominator using their prime factors.

$\displaystyle \frac{24}{60}=\frac{2 \cdot 2 \cdot 2 \cdot 3}{2 \cdot 2 \cdot 3 \cdot 5}$

Then cross out the prime factors common to the numerator and the denominator.

$\displaystyle \frac{24}{60}=\frac{\not 2 \cdot \not 2 \cdot 2 \cdot \not 3}{\not 2 \cdot \not 2 \cdot \not 3 \cdot 5}=\frac{2}{5}$

The product of the prime factors that are crossed out is $2 \cdot 2 \cdot 3=12$ , which is the greatest common divisor of 24 and 60.

Thus the greatest common divisor of two integers $a$ and $b$ is the product of the prime factors shared by the two numbers. This approach of finding the greatest common divisor depends on performing prime factorization, which is a hard problem for larger numbers. This approach, though conceptually clear, is clearly not efficient.

We need an algorithm for finding the greatest common divisor that does not require prime factorization. First, we have another discussion on the greatest common divisor.

___________________________________________________________________________________________________________________

The Greatest Common Divisor

Let $a$ and $b$ be integers. We say that $a$ divides $b$ (denoted by $a \ \lvert \ b$ ) if there is an integer $q$ such that $b=q \cdot a$ . In other words, $a \ \lvert \ b$ if $a$ divides $b$ without leaving a remainder. For examples, $3 \ \lvert \ 18$ and $7 \ \lvert \ 91$ . When $a$ does not divide $b$ , we write $a \not \lvert \ b$ .

The greatest common divisor (or GCD) of two integers $a$ and $b$ is denoted by $\text{GCD}(a,b)$ and is the largest positive integer that divides both $a$ and $b$ . It is clear that $\text{GCD}(a,b)$ is the positive integer $d$ such that

$d \lvert a$ and $d \lvert b$ .
If $c \lvert a$ and $c \lvert b$ , then $c \le d$ .

The greatest common integer $\text{GCD}(a,b)$ is always uniquely defined. Each integer has only finitely many integer divisors. So there are only finitely many divisors common to both $a$ and $b$ (the integer 1 is one of them). Any finite set of real numbers has a unique largest element. Thus among all the common divisors of $a$ and $b$ , there is the largest one, which we denote by $\text{GCD}(a,b)$ . Consequently, $\text{GCD}(a,b) \ge 1$ .

We can observe that the greatest common integer $\text{GCD}(a,b)$ defined in this section is identical to the product of the prime factors shared by the two integers $a$ and $b$ .

To perform the Euclidean algorithm, we need the division algorithm and the following lemma.

Division Algorithm
Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r <b$ .

Lemma 1
Let $a$ and $b$ be positive integers. If $a=q \cdot b+r$ , then $\text{GCD}(a,b)=\text{GCD}(b,r)$ .

For the discussion in this post, Lemma 1 is used in conjunction with the division algorithm. So we put Lemma 1 in words in the context of applying the division algorithm as follows.

Lemma 1. When $a$ is divided by $b$ , the GCD of $a$ and $b$ is the same as the GCD of the $b$ (the divisor) and the $r$ (the remainder).

Proof of Lemma 1

Suppose that $a=q \cdot b+r$ . Let $h=\text{GCD}(a,b)$ and $k=\text{GCD}(b,r)$ .

We first show that $h \le k$ . Since $a=q \cdot b+r$ and since $h \ \lvert \ a$ and $h \ \lvert \ b$ , we have $h \ \lvert \ r$ . Since $h$ is a common divisor of $b$ and $r$ , $h \le k$ .

Now we show $k \le h$ . Since $a=q \cdot b+r$ , it follows that $k$ is a common divisor of $a$ and $b$ . Thus $k \le h$ . $\blacksquare$

___________________________________________________________________________________________________________________

Example for the Euclidean Algorithm

Before defining the Euclidean algorithm, let’s look at an example. Find the greatest common divisor of $1638$ and $357$ .

The Euclidean algorithm can be implemented using subtraction or division.

In the subtraction implementation, the Euclidean algorithm starts with a pair of positive integers and forms a new pair that consists of the smaller integer and the difference between the larger and smaller integers. The process repeats until the two integers are equal. That number then is the greatest common divisor of the original pair.

The following series of subtractions derives the GCD of $1638$ and $357$ .

$\displaystyle (1) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&1281&\text{ }&357 \\ 3&\text{ }&924&\text{ }&357 \\ 4&\text{ }&567&\text{ }&357 \\ 5&\text{ }&210&\text{ }&357 \\ 6&\text{ }&210&\text{ }&147 \\ 7&\text{ }&63&\text{ }&147 \\ 8&\text{ }&63&\text{ }&84 \\ 9&\text{ }&63&\text{ }&21 \\ 10&\text{ }&42&\text{ }&21 \\ 11&\text{ }&21&\text{ }&21 \end{bmatrix}$

In the above table, to go from one row to the next, the larger number is reduced by the smaller number. The process stops when the two numbers are equal. In this example, the greatest common divisor is $21$ .

Note that the above subtraction process can be speeded up by doing division instead. For example, in the above table, you can jump from row 1 to row 5 by applying the division algorithm. The following is the same example using the division implementation.

$\displaystyle (2) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&210&\text{ }&357 \\ 3&\text{ }&210&\text{ }&147 \\ 4&\text{ }&63&\text{ }&147 \\ 5&\text{ }&63&\text{ }&21 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

To go from row 1 to row 2, divide $1638$ by $357$ to obtain the remainder $210$ . To go from row 2 to row 3, divide the larger number $357$ by $210$ to obtain the remainder $147$ . Repeat the process until one of reaching the remainder of zero. Then the other number in the last row is the greatest common divisor. The following is the same algorithm with the divisions added.

$\displaystyle (3) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2}&\text{ }&\text{Division} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357&\text{ }&1638=4 \cdot 357+210 \\ 2&\text{ }&210&\text{ }&357&\text{ }&357=1 \cdot 210+147 \\ 3&\text{ }&210&\text{ }&147&\text{ }&210=1 \cdot 147+63 \\ 4&\text{ }&63&\text{ }&147&\text{ }&147=2 \cdot 63+21 \\ 5&\text{ }&63&\text{ }&21&\text{ }&63=3 \cdot 21+0 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

As shown in the example, the Euclidean algorithm only requires subtractions or divisions and no prime factorization. Note that Lemma 1 is used throughout the two tables. Let’s look at table (3). Because the GCD of two numbers is the same as the divisor and the remainder (Lemma 1), the GCD of any row is identical to the GCD of the row below.

___________________________________________________________________________________________________________________

The Euclidean Algorithm

In the remainder of the post, we only discuss the division implementation of the Euclidean algorithm. The following is the description of the Euclidean algorithm.

Euclidean Algorithm

Let $a_0$ and $b_0$ be positive integers. Assume $b_0<a_0$ . Start with the pair $(a_0,b_0)$ and forms a new pair that consists of the smaller number and the remainder derived from dividing the larger number by the smaller. The process stops when reaching a remainder of zero. Then the other number in the last pair is the GCD of $a_0$ and $b_0$ .

To describe using some notations, we have the following divisions.

$a_0=q_0 \cdot b_0+r_0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_0<b_0$

$b_0=q_1 \cdot r_0+r_1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_1<r_0$

$r_0=q_0 \cdot r_1+r_2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_2<r_1$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$r_k=q_k \cdot r_{k+1}+r_{k+2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_{k+2}<r_{k+1}$

The above series of divisions will stop at some $k=j$ where the remainder $r_{j+2}=0$ . We have $r_j=q_j \cdot r_{j+1}$ where $r_{j+1}$ is the GCD of the original pair $(a_0,b_0)$ .

Proof of Euclidean Algorithm
In the above notation, the sequence of non-negative numbers $b_0>r_0>r_1>r_2>\cdots$ must stop at some point. Eventually $r_{j+2}=0$ for some $j$ . We have $r_j=q_j \cdot r_{j+1}+0$ . Then $\text{GCD}(r_j,r_{j+1})=\text{GCD}(r_{j+1},0)=r_{j+1}$ .

Applying Lemma 1 repeatedly, we have:

$\displaystyle \begin{aligned} r_{j+1}&=\text{GCD}(r_{j+1},0) \\&=\text{GCD}(r_j,r_{j+1}) \\&\cdots \\&\cdots \\&\cdots \\&=\text{GCD}(r_1,r_{2}) \\&=\text{GCD}(r_0,r_{1}) \\&=\text{GCD}(b_0,r_{0}) \\&=\text{GCD}(a_0,b_{0}) \end{aligned}$

Comment. Note that the statement of the Euclidean algorithm starts with a pair of positive integers $(a_0,b_0)$ . If either number is negative, we can take the absolute value of the numbers and the resulting GCD is the same as the original pair. This follows from the following fact.

$\text{GCD}(a,b)=\text{GCD}(-a,b)=\text{GCD}(a,-b)=\text{GCD}(-a,-b)$

___________________________________________________________________________________________________________________

The Extended Euclidean Algorithm

Another good use of the Euclidean algorithm is to find integer solutions to the linear equation $ax+by=d$ where $d=\text{GCD}(a,b)$ . This is called the extended Euclidean algorithm. We state it in the following lemma.

Lemma 2 (The Extended Euclidean Algorithm)
Let $a$ and $b$ be integers. Let $d=\text{GCD}(a,b)$ . Then there are integers $x$ and $y$ that satisfies the equation $ax+by=d$ .

Proving Lemma 2 is a matter of working the Euclidean algorithm backward. We demonstrate the idea using our example of $a=1638$ and $b=357$ . The following shows the divisions used in Table (3) above.

$1638=4 \cdot 357+210$
$357=1 \cdot 210+147$
$210=1 \cdot 147+63$
$147=2 \cdot 63+21$
$63=3 \cdot 21+0$

We start off with the second to the last division and work backward.

$\displaystyle \begin{aligned} 21&=147-2 \cdot 63 \\&=147 - 2 \cdot (210-147) \\&=3 \cdot 147-2 \cdot 210 \\&=3 \cdot (357-210)-2 \cdot 210 \\&=3 \cdot 357 -5 \cdot 210 \\&=3 \cdot 357- 5 \cdot (1638- 4 \cdot 357) \\&=(-5) \cdot 1638+23 \cdot 357 \end{aligned}$

The equation $1638x+357y=21$ has solution $x=-5$ and $y=23$ .

As an application to the extended Euclidean algorithm, we have the following corollary.

Corollary 3
Let $a$ and $b$ be integers. Let $h=\text{GCD}(a,b)$ . Then if $k$ is a common divisor of $a$ and $b$ , then $k$ is a divisor of $h$ .

Proof of Corollary
According to Lemma 2, there are integers $x$ and $y$ such that $ax+by=h$ . Note that $k$ divides each term on the left-hand side of this equation. So $k$ divides $h$ as well. $\blacksquare$
___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

The Division Algorithm

Posted on July 27, 2013 by Dan Ma

The division algorithm is the conceptual underpinning of many concepts in number theory (congruence arithmetic is one example). In this post, we present a proof of the division algorithm and connect it to one important property of congruence.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

The Division Algorithm

The following is the statement of the division algorithm.

Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r <b$ .

Let $A$ be the set $A=\left\{a-jb: j=0,1,2,3,\cdots \right\}$ . Let $A_+$ be the following subset of $A$ .

$A_+=\left\{x \in A: x \ge 0 \right\}$

The set $A_+$ is a set of non-negative integers. Hence it must have a least element, say $r$ . Then we have $r=a-qb$ for some positive integer $q$ . Furthermore, we have $0 \le r<b$ . If $r>b$ , $r$ would not be the least element of $A_+$ since we can subtract $b$ into $r$ to obtain $a-(q+1)b$ , which is less than $r$ and is an element of $A_+$ .

We now have found integers $q$ and $r$ such that $a = q \cdot b + r$ . It remains to show that the integers $q$ and $r$ are unique. Suppose there are also integers $q_0$ and $r_0$ such that

$a=q \cdot b + r=q_0 \cdot b + r_0$

After subtracting, $(q-q_0) \cdot b + (r-r_0)=0$ . Since $b$ divides both $0$ and $(q-q_0) \cdot b$ , $b$ must divides $r-r_0$ . This means that $r-r_0=0$ , since both $r$ and $r_0$ are non-negative integers that are less than $b$ . Thus $r=r_0$ and in turns $q-q_0$ . $\blacksquare$

Conceptually the division algorithm tells us that there is a unique remainder $r$ upon division of $a$ by $b$ . In terms of actual computation, it does not tell us how to find the remainder or the quotient. However it is the conceptual underpinning of many concepts and ideas in number theory.

___________________________________________________________________________________________________________________

Congruence

We now use the division algorithm to prove one important property of congruence. The symbol $a \equiv b \ (\text{mod} \ m)$ means that $m$ divides $a-b$ (in words, we say $a$ is congruent to $b$ modulo $m$ ). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.

For every integer $a$ , $a \equiv r \ (\text{mod} \ m)$ for a unique integer $r$ with $0 \le r<m$ .

In other words, any integer is congruence modulo $m$ to one and only one element $r$ in the set $\left\{0,1,2,\cdots,m-1 \right\}$ . The integer $r$ is called the least residue of $a$ modulo $m$ .

The above property about least residue follows from the division algorithm. Let $a$ be any integer. If $a=0$ , clearly $a \equiv 0 \ (\text{mod} \ m)$ . We can assume that $a \ne 0$ .

Now consider the case that $a>0$ . By the division algorithm, there are integers $q$ and $r$ such that $a=q \cdot m+r$ where $0 \le r <m$ . Thus $a \equiv r \ (\text{mod} \ m)$ .

Consider the case that $a<0$ . By the division algorithm, there are integers $q$ and $r$ such that $-a=q \cdot m+r$ where $0 \le r <m$ . Immediately we have $a=(-q) \cdot m+(-r)$ . Thus $a \equiv -r \ (\text{mod} \ m)$ . Note that $-r \equiv m-r \ (\text{mod} \ m)$ . Thus $a \equiv m-r \ (\text{mod} \ m)$ /

One concluding remark is that any least residue that is found in the above argument is unique. This is because no two distinct elements of the set $\left\{0,1,2,\cdots,m-1 \right\}$ can be congruent to each other. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

A basic discussion of congruences

Posted on July 22, 2013 by Dan Ma

When performing the division $45 \div 7$ , the remainder is $3$ . What is the remainder in the division $9664^{79081} \div 55049$ ? What is the remainder in the division of $(2^{57885161} - 1)$ by $524287$ ? If you have special software, you can determine quickly that the remainder for the first question is the number $1020$ . Note that the number $2^{57885161} - 1$ in the second question is the current largest known prime number at the writing of this post. The special software you use might have to struggle a little to come up with the answer of $255$ . Without special software, you can use congruence arithmetic to perform the above calculations.

Congruence notation was invented by the great mathematician Carl Friedrich Gauss (1777 – 1855). It is hard to overstate the importance of the role of congruence in number theory. The notion not only eases calculation but also makes statements of theorems much easier to state and simplifies the proofs of theorems. This post is a basic discussion of congruence.

For more information about congruence or modular arithmetic, see the number theory introductory text [1] or the Wikepedia entry on modular arithmetic.

___________________________________________________________________________________________________________________

Basic Discussion

Given integers $a$ , $b$ and $m$ with $m>0$ , the statement that $a$ is congruent to $b$ modulo $m$ means that the difference $a-b$ is divisible by $m$ . In symbol, we write $a \equiv b \ (\text{mod} \ m)$ . The number $m$ is the modulus of the congruence. We also use the notation $m \lvert a-b$ to refers to the statement that $a-b$ is divisible by $m$ . We repeat the definition below.

$a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ m \lvert a-b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The following two properties of congruence that can be easily verified from definition $(1)$ .

$a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ a=b+k \cdot m \text{ for some integer } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2a)$

$b+k \cdot m \equiv b \ (\text{mod} \ m) \text{ for all integers } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2b)$

Another meaning of congruence modulo $m$ comes from the division algorithm. For example, the division $45 \div 7$ gives the remainder $3$ , i.e., $45=6 \cdot 7 +3$ . So for the division $a \div m$ where both $a$ and $m$ are both positive, we have $a=q \cdot m+r$ for some integer $r$ with $0 \le r <m$ (call the remainder) and some integer $q$ . From this we can conclude that every integer $a$ is congruent modulo $m$ to exactly one integer from the set $\left\{0,1,2,\cdots,m-1 \right\}$ . The integer $r$ is called the least residue of $a$ modulo $m$ . We summarize as follows: for every integer $a$ ,

$a \equiv r \ (\text{mod} \ m) \text{ for a unique integer } r \text{ with } 0 \le r < m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

For a proof of property (3), see this post. Another characteristic of congruence modulo $m$ is the following property.

$a \equiv b \ (\text{mod} \ m) \Longleftrightarrow \text{ each of } a \text{ and } b \text{ leaves the same remainder }$

$\text{ when divided by } m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

All the above conditions point to the cyclical nature of congruence, which can be visualized in a diagram. The figure is below describes congruence modulo $12$ .

You can start at any point in the above diagram. Every time you add or subtract the modulus $m=12$ , you go around the circle and come back to the same point you start from (conditions 2 and 4). Two integers are related congruence modulo $12$ if they can be reduced by the division algorithm to the same time in the clock (condition 3).

___________________________________________________________________________________________________________________

Some Properties for Congruence

Congruence arithmetic is similar to conventional arithmetic. However, there are important differences. For example, comparing congruence with the equality sign = will help us see some of the differences. To set up the comparison, the following are some operations on real numbers we would like to focus on:

Operations on real numbers:

$a=b \ \ \Longrightarrow \ \ b=a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R1}$

$a=b \text{ and } b=c \ \ \Longrightarrow \ \ a=c \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R2}$

$a=b \text{ and } c=d \ \ \Longrightarrow \ \ a+c=b+d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R3}$

$a=b \text{ and } c=d \ \ \Longrightarrow \ \ a \cdot c=b \cdot d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R4}$

$ac=bc \text{ and } c \ne 0 \ \ \Longrightarrow \ \ a=b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R5}$

All the above arithmetic operations on real numbers have analog in congruence except for R5. The following are the equivalence in congruence operations.

$a \equiv b \ (\text{mod} \ m) \ \ \Longrightarrow \ \ b \equiv a \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C1}$

$a \equiv b \ (\text{mod} \ m) \text{ and } b \equiv c \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv c \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C2}$

$a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a+c \equiv b+d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C3}$

$a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \cdot c \equiv b \cdot d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C4}$

$a \cdot c \equiv b \cdot c \ (\text{mod} \ m) \text{ and } c \not \equiv 0 \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv b \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C5}$

$c$

$m$

The properties C3 and C4 indicate that congruences may be validly added, subtracted and multiplied.

Note that the direct analog of R5 is not true in general. For example, $20 \equiv 2 \ (\text{mod} \ 6)$ . However, $10 \not \equiv 1 (\text{mod} \ 6)$ . In this case we cannot cancel out the common factor of $2$ on both sides of the congruence. When the additional requirement that the common factor $c$ and the modulus $m$ are coprime (i.e. the greatest common divisor is $1$ ), we can cancel out the common factor (as indicated by C5).

The derivation of the properties C1 through C4 is straightforward. The proof of C5 relies on Euclid’s lemma.

___________________________________________________________________________________________________________________

Some Examples

The properties in the above section are not meant to be memorized. The best approach is to work examples.

One typical congruence calculation is to find the least residue of a number $a$ modulo $m$ . The number $a$ could be a sum or a product. Or it could be some number raised to an exponent. For the case of sum or product, we can start by reducing the components in the sum or product. For the case of an exponential, we can sometimes break it up into product of smaller numbers or use a “divide and conquer” approach. Let’s look at some examples.

To find $55 \cdot 67$ congruence modulo $7$ , we do not need to first multiply. We can start by reducing each of the factors as follows:

$55 \cdot 67 \equiv 6 \cdot 4 \equiv 24 \equiv 3 \ (\text{mod} \ 7)$

In the above calculation we use property C4. We have $55 \equiv 6 \ (\text{mod} \ 7)$ and $67 \equiv 4 \ (\text{mod} \ 7)$ . Thus $55 \cdot 67 \equiv 6 \cdot 4 \ (\text{mod} \ 7)$ . We really do not need to be too conscious of which property to use. Just work enough examples and the process will flow quite naturally.

To find $1567 \equiv (\text{mod} \ 13)$ , we can start by breaking up the number $1567$ . The following is one example of how to do so.

$\displaystyle \begin{aligned} 1567&=30 \cdot 50 + 67 \\&=31 \cdot 50 + 17 \\&\equiv 5 \cdot 11+4=59 \ (\text{mod} \ 13)\\&=50+9 \\&\equiv 11+9 \ (\text{mod} \ 13)=20 \\&\equiv 7 \ (\text{mod} \ 13) \end{aligned}$

In the above calculation, we break up $1567$ into multiple of $50$ with $17$ added. Then starting reducing each of the numbers. Then multiply and sum to get $59$ . We then break it up into $50$ and $9$ , which is reduced into $11$ and $9$ . Finally $20$ is reduced into $7$ modulo $13$ . The properties used are C3 and C4. Once again, this type of calculation will flow naturally after working a few examples.

To find $55^{23} \equiv (\text{mod} \ 7)$ , we can start by reducing the base $55$ .

$\displaystyle \begin{aligned} 55^{23}&\equiv 6^{23} \ (\text{mod} \ 7) \\&=(6^2)^{11} \cdot 6 \\&\equiv (1)^{11} \cdot 6 \ (\text{mod} \ 7) \\&\equiv 6 \ (\text{mod} \ 7) \end{aligned}$

It follows from property C4 that if $a \equiv b \ (\text{mod} \ m)$ , then $a^n \equiv b^n \ (\text{mod} \ m)$ . Based on this idea, we can reduce base $55$ to the smaller base of $6$ . We then reduce the exponent $23$ to the exponent of $11$ . Such a process is a “divide and conquer” process that repeatedly reduces the exponent by half down to a manageable size.

Another example. Find the $2^{100} \equiv (\text{mod} \ 101)$ . Note that $2^7=128$ and $128 \equiv 27 \ (\text{mod} \ 101)$ .

$\displaystyle \begin{aligned} 2^{100}&= (2^{7})^{14} \cdot 2^2 \\&\equiv (27)^{14} \cdot 4 \ (\text{mod} \ 101) \\&= (27^2)^{7} \cdot 4 \\&\equiv 22^7 \cdot 4 \ (\text{mod} \ 101) \\&=(22^2)^3 \cdot 22 \cdot 4 \\&\equiv 80^3 \cdot 88 \ (\text{mod} \ 101) \\&=80^2 \cdot 80 \cdot 88 \\&\equiv 37 \cdot 80 \cdot 88 \ (\text{mod} \ 101) \\&=2960 \cdot 88 \\&\equiv 31 \cdot 88 \ (\text{mod} \ 101) \\&\equiv 1 \ (\text{mod} \ 101) \end{aligned}$

The key to a reduction of power in a congruence calculation is to find the right starting point. In the above example, exponent is reduced from $100$ to $14$ , Then subsequently, keep reducing the exponent by half in each step until reaching a size that is manageable or easy to do.

It also follows from Fermat’s little theorem that $2^{100} \equiv 1 \ (\text{mod} \ 101)$ .

___________________________________________________________________________________________________________________

More Examples

It is well known, even to some elementary school children, that an integer is divisible by nine if the sum of the digits is divisible by nine. The proof of this fact is very easy if done using congruence. The idea for the proof will be clear from the following example.

The number $55953$ is divisible by nine since $55953 = 9 \cdot 6217$ . Also note that the sum of its digits is $27$ . We can also look at the congruence angle. First, $10 \equiv 1 \ (\text{mod} \ 9)$ , $10^2 \equiv 1 \ (\text{mod} \ 9)$ and $10^3 \equiv 1 \ (\text{mod} \ 9)$ and so on. Furthermore, we have:

$55953=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3$

We can now reduce the digital representation of $55953$ using congruence.

$\displaystyle \begin{aligned} 55953&=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3 \\&\equiv 5 \cdot 1+5 \cdot 1+9 \cdot 1+5 \cdot 1+3 \\&=27 \\&\equiv 0 \ (\text{mod} \ 9) \end{aligned}$

The above derivation shows that any positive integer is congruent modulo $9$ to the sum of its digits. Thus a positive integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$ .

The same property is also true for divisibility by three. Using congruence, it can be shown that any positive integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$ .

Congruence modulo $11$ is an interesting case. Note that $10 \equiv -1 \ (\text{mod} \ 11)$ , $10^2 \equiv 1 \ (\text{mod} \ 11)$ , and $10^3 \equiv -1 \ (\text{mod} \ 11)$ and so on. Thus $10^n \equiv k \ (\text{mod} \ 11)$ where $k=1$ or $k=-1$ depending on whether the power is even or odd. So in reducing the digital representation of a number, we need to add alternating plus and minus signs.

$\displaystyle \begin{aligned} 85647&=8 \cdot 10^4+5 \cdot 10^3+6 \cdot 10^2+4 \cdot 10+7 \\&\equiv 8 \cdot 1+5 \cdot (-1)+6 \cdot 1+4 \cdot (-1)+7 \\&=12 \\&\equiv 1 \ (\text{mod} \ 11) \end{aligned}$

Thus $85647$ is not divisible by $11$ .

___________________________________________________________________________________________________________________

Exercises

Work the two congruence calculation mentioned at the beginning of the post. Show the following.

$9664^{79081} \equiv 1020 \ (\text{mod} \ 55049)$

$2^{57885161}-1 \equiv 255 \ (\text{mod} \ 524287)$

___________________________________________________________________________________________________________________

Reference

Dudley U., Elementary Number Theory, 2nd ed., Dover Publications, Inc, New York, 2008

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

An observation about Mersenne primes

Posted on July 20, 2013 by Dan Ma

This post concerns an observation about Mersenne primes. The observation will be made after presenting an example.

Mersenne numbers are integers of the form $M_n=2^n-1$ where $n$ is a positive integer. If $M_n$ is a prime number, then $M_n$ is said to be a Mersenne primes. Not all Mersenne numbers are prime. Are there infinitely many Mersenne primes? No one has yet been able to resolve this question. As of the writing of this post, there are only 48 known Mersenne primes, the largest of which is $M_p$ where $p=57885161$ , discovered in January 25, 2013. The current largest known Mersenne prime is also the current largest known prime number.

___________________________________________________________________________________________________________________

Example

In this example, $p=57885161$ . Since $M_p$ is prime, it is obviously not divisible by any other prime numbers. In particular, $M_p$ is not divisible by any smaller Mersenne primes. We demonstrate this using congruence modulo arithmetic.

We wish to point out that we are not trying to establish the primality of $M_p$ (doing that would take a great amount of super computing resources). This is merely a simple example of working with Mersenne primes and an exercise in doing congruence modulo calculation.

First, show that $M_p=2^p-1$ is not divisible by the Mersenne prime $2^{19}-1=524287$ .

If $M_p=2^p-1$ is divisible by $2^{19}-1$ , $M_p \equiv 0 \ (\text{mod} \ 2^{19}-1)$ . So we need to show $2^p-1 \not \equiv 0 \ (\text{mod} \ 2^{19}-1)$ or $2^p \not \equiv 1 \ (\text{mod} \ 2^{19}-1)$ .

Note that $2^{19} \equiv 1 \ (\text{mod} \ 2^{19}-1)$ . So it is a matter of subtracting the largest multiple of 19 out of the exponent $p=57885161$ . We have $p=57885161=3046587 \cdot 19+8$ . We have the following congruence calculation.

$2^{57885161}=(2^{19})^{3046587} \cdot 2^8 \equiv (1)^{3046587} \cdot 2^8=2^8=256 \ (\text{mod} \ 2^{19}-1)$

Since $2^p \equiv 256 \ (\text{mod} \ 2^{19}-1)$ and $256 \ne 1$ , $M_p=2^p-1$ is not divisible by $2^{19}-1=524287$ .

The number $2^{3217}-1$ is also a Mersenne prime. To show that $M_p=2^p-1$ is not divisible by $2^{3217}-1$ , we only need to show $2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1)$ .

Note that $2^{3217} \equiv 1 \ (\text{mod} \ 2^{3217}-1)$ . We have $p=57885161=17993 \cdot 3217 + 1680$ . After subtracting multiple of $3217$ , we have the remainder $1680$ . Thus $2^{57885161}$ congruence modulo $2^{3217}-1$ is reduced to $2^{1680}$ congruence modulo $2^{3217}-1$ .

$2^{57885161} \equiv 2^{1680} \ (\text{mod} \ 2^{3217}-1)$

Since $2^{1680}>1$ , $2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1)$ . Thus $M_p=2^p-1$ is not divisible by $2^{3217}-1$ .

___________________________________________________________________________________________________________________

An Observation

The above examples lead to the following observation.

If $a$ and $b$ are prime numbers such that $a<b$ , then $2^a-1$ is not a divisor of $2^b-1$ .

As in the examples, we need to show $2^b \not \equiv 1 \ (\text{mod} \ 2^a-1)$ . Note that $2^a \equiv 1 \ (\text{mod} \ 2^a-1)$ . According to the division algorithm, we have $b=r + a \cdot k$ where $k$ is some integer and $r$ is the remainder with $0 \le r <a$ . The remainder $r$ cannot be zero. If it is, $a$ would divide $b$ . But this cannot be since both of them are prime numbers. Since $r \ne 0$ , $2^r>1$ . We have the following congruence calculation.

$2^b = (2^a)^{k} \cdot 2^r \equiv 2^r \ (\text{mod} \ 2^a-1)$

Since $2^r>1$ , $2^b \not \equiv 1 \ (\text{mod} \ 2^a-1)$ . Thus $2^b-1$ is not divisible by $2^a-1$ .

The above derivation is definitely a much cleaner demonstration than the derivations shown in the above examples.

Another way to state the above statement is that no Mersenne number can be divisible by any smaller Mersenne number.

Note that in the above statement, $2^a-1$ and $2^b-1$ do not need to be primes. Only the exponents $a$ and $b$ need to be primes. There are many Mersenne numbers that are not prime numbers. The smallest is $2^{11}-1=28*89$ . Other smaller non-prime Mersenne numbers are $2^{23}-1$ and $2^{29}-1$ .

So the above statement says that even when a Mersenne number is composite, it cannot have factors of the form $2^a-1$ . It can certainly not have factors in the form of a Mersenne prime. In testing whether $2^b-1$ is a prime, it can be safe to skip any smaller number of the form $2^a-1$ . This fact could be useful in testing the primality of a Mersenne number (at least marginally useful).

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

How to toss a coin

Posted on July 14, 2013 by Dan Ma

In this post, we demonstrate how to simulate a random coin toss using a cryptographic algorithm that was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm). Tossing a coin using a cryptographic algorithm is an example of a game of mental poker.

The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).

___________________________________________________________________________________________________________________

Setting the Algorithm

A full discussion of the algorithm used here can be found in the previous post Fermat’s Little Theorem and Mental Poker.

Andy and Becky are in different locations and they would like to simulate a random coin toss. First they need to agree on two positive integers that are to represent head and tail, say $m_h$ for head and $m_t$ for tail. These two numbers should be less than the prime number $p$ discussed in the next paragraph.

They now need to encrypt the numbers before tossing the coin. Both players agree on a large prime number $p$ . If the goal of preventing or minimizing cheating is important, the players should choose a prime number that is as large as feasible computationally speaking.

With the prime number $p$ decided, each of the players chooses an encryption-decryption key, which is a pair of positive integers $x_0$ and $x_1$ such that

$x_0 \cdot x_1 \equiv 1 \ (\text{mod} \ p-1)$ ,

meaning that $x_0 \cdot x_1=1+(p-1) \cdot k$ for some integer $k$ .

Each of the players chooses such a pair of numbers. In terms of notation, Andy chooses $a_0$ and $a_1$ . Becky chooses $b_0$ and $b_1$ . Each player chooses the number pair independently and keeps it secret from the other player.

The number with the $0$ -subscript is the encryption key and the number with the $1$ -subscript is the decryption key. The following are the encryption functions, expressed in congruence modulo $p$ , for Andy and Becky, respectively.

$f_a(m) \equiv m^{a_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}$

$f_b(m) \equiv m^{b_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}$

For example, if Andy wants to encrypt the number $m$ , he raises $m$ to the power of $a_0$ and looks for the remainder upon division by $p$ . The remainder will be denoted by $f_a(m)$ . The function $f_b(m)$ works similarly for Becky.

The following are the decryption functions, expressed in congruence modulo $p$ , for Andy and Becky, respectively.

$g_a(c) \equiv c^{a_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}$

$g_b(c) \equiv c^{b_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}$

For example, if Andy wants to decrypt the number $c=f_a(m)$ , he raises $c$ to the power of $a_1$ and looks for the remainder upon division by $p$ . The remainder will be denoted by $g_a(m)$ , which will be the original number $m$ . The proof of this fact is based on the Fermat’s Little Theorem (see the previous post Fermat’s Little Theorem and Mental Poker).

The function $g_b(m)$ works similarly for Becky.

___________________________________________________________________________________________________________________

A Numerical Example

For illustration, we use a small prime number. We use $p=7919$ . We emphasize that this is just for illustration. In an application where the chance for cheating is to be minimized, a large prime number should be used.

Andy and Becky use the following assignment for Head and Tail.

For this illustration, Andy chooses $a_0=\text{47}$ and $a_1=\text{52,899}$ by letting $k=\text{314}$ in the equation below. Becky chooses $b_0=\text{71}$ and $b_1=\text{26,319}$ by letting $k=\text{236}$ in the following equation.

$x_0 \cdot x_1=1+7918 \cdot k$

Andy and Becky choose these keys independently and they keep them secret without letting the other person know. Andy encrypts both the head and tail numbers as follows:

$2500^{47} \equiv 7518=f_a(2500) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

The encrypted numbers and the original numbers are displayed in the following table.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Andy}&\text{ }&\text{7,518}&\text{ }&\text{698} \end{bmatrix}$

Of course, the above table is kept secret from Becky. However, the encrypted numbers (just the encrypted numbers) are sent to Becky for random selection.

Becky selects one of the encrypted numbers for herself (perhaps thru a coin toss). Then the other encrypted number is the choice for Andy. Suppose Becky selects $7518$ . Becky then encrypted the number $7518$ using her key.

$7518^{71} \equiv 1341=f_b(7518) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Becky passes the encrypted number $1341$ (her selection) and $698$ (Andy’s selection) back to Andy. The following table lists out the numbers received by Andy.

Andy decrypts his number $698$ and gets back $2500$ , which is tail. He also decrypts $1341$ and obtains $223$ , which he passes back to Becky.

$698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

$1341^{52899} \equiv 223=g_a(1341) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)$

The following summarizes the results up to this point.

Once Becky gets the decrypted number $223$ from Andy, she decrypts it using her own key to obtain $2500$ , which is a head.

$223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)$

The following table summarizes the results of the coin toss.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{2,500} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Results of Coin Toss}&\text{ }&\text{5,000}&\text{ }&\text{2,500} \end{bmatrix}$

___________________________________________________________________________________________________________________

Numerical Calculation

We now show some of the calculations involved in the above encryption and decryption. We show three calculations.

$5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

$698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

$223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)$

Even with the small prime number $p=7919$ , the calculation is not done directly. For example, unless special software is used, $f_a(5000)$ is not found by calculating $5000^{47}$ and then finding the remainder upon division by $7919$ . The following demonstrates a “divide and conquer” approach for the calculation for $(2)$ where in each step the exponent is reduced by half.

$\displaystyle \begin{aligned} 5000^{47}&\equiv (5000^2)^{23} \cdot 5000 \ (\text{mod} \ 7919) \\&\text{ } \\&=7636^{23} \cdot 5000 \equiv (7636^2)^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 2501 \equiv (899^2)^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 7322 \equiv (463^2)^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 754 \\&\text{ } \\&\equiv 295 \cdot 754 \\&\text{ } \\&\equiv 698 \ (\text{mod} \ 7919) \end{aligned}$

In each step in the above calculation, we use the division algorithm to obtain the remainder. For example, to go from the first line to the second line, divide $5000^2$ by $7919$ to obtain the remainder of $7636$ . The number $698$ in the last step is the remainder when $295 \cdot 754$ is divided by $7919$ . These calculations are tedious if done by hand and should be done by computer.

The calculation for $(4)$ is that $698^{52899} \equiv 5000 \ (\text{mod} \ 7919)$ . In other word, decrypting the encrypted number of $698$ recovers the original number of $5000$ . This calculation can be shortened by using Fermat’s Little Theorem, which implies that $698^{7919-1} \equiv 1 \ (\text{mod} \ 7919)$ . Thus we have:

$698^{47508} \equiv 698^{6 \cdot 7918} \equiv 1 \ (\text{mod} \ 7919)$

So we can reduce $47508$ from the exponent $52899$ , leaving the exponent $5391$ . We have:

$698^{52899} \equiv 698^{47508} \cdot 698^{5391} \equiv 1 \cdot 698^{5391} \ (\text{mod} \ 7919)$

The following uses the “divide and conquer” approach to compute $698^{5391}$ modulo $7919$ .

$\displaystyle \begin{aligned} 698^{5391}&\equiv (698^2)^{2695} \cdot 698 \ (\text{mod} \ 7919) \\&\text{ } \\&=4145^{2695} \cdot 698 \equiv (4145^2)^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 2775 \equiv (4714^2)^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 7081 \equiv (1082^2)^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 3969 \equiv (6631^2)^{168} \cdot 3969 \\&\text{ } \\&\equiv 3873^{168} \cdot 3969 \equiv (3873^2)^{84} \cdot 3969 \\&\text{ } \\&\equiv 1543^{84} \cdot 3969 \equiv (1543^2)^{42} \cdot 3969 \\&\text{ } \\&\equiv 5149^{42} \cdot 3969 \equiv (5149^2)^{21} \cdot 3969\\&\text{ } \\&\equiv 7308^{21} \cdot 3969 \equiv (7308^2)^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 6074 \equiv (1128^2)^{5} \cdot 6074\\&\text{ } \\&\equiv 5344^5 \cdot 6074 \equiv (5344^2)^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv 2422^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv2422^2 \cdot 7394 \\&\text{ } \\&\equiv 6024 \cdot 7394 \\&\text{ } \\&\equiv 5000 \ (\text{mod} \ 7919) \end{aligned}$

The calculation for $(6)$ is $223^{26319} \equiv 2500 \ (\text{mod} \ 7919)$ . We can also get an assist from the Fermat’s Little Theorem. In this particular case, $223^{7918} \equiv 1 \ (\text{mod} \ 7919)$ . With $26319=3 \cdot 7918+2565$ , we only need to calculate $223^{2565} \ (\text{mod} \ 7919)$ , which is done below.

$\displaystyle \begin{aligned} 223^{2565}&\equiv (223^2)^{1282} \cdot 223 \ (\text{mod} \ 7919) \\&\text{ } \\&=2215^{1282} \cdot 223 \equiv (2215^2)^{641} \cdot 223 \\&\text{ } \\&\equiv 4364^{641} \cdot 223 \equiv (4364^2)^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 7054 \equiv (7220^2)^{160} \cdot 7054 \\&\text{ } \\&\equiv 5542^{160} \cdot 7054 \equiv (5442^2)^{80} \cdot 7054 \\&\text{ } \\&\equiv 3882^{80} \cdot 7054 \equiv (3882^2)^{40} \cdot 7054 \\&\text{ } \\&\equiv 67^{40} \cdot 7054 \equiv (67^2)^{20} \cdot 7054 \\&\text{ } \\&\equiv 4489^{20} \cdot 7054 \equiv (4489^2)^{10} \cdot 7054\\&\text{ } \\&\equiv 5185^{10} \cdot 7054 \equiv (5185^2)^{5} \cdot 7054 \\&\text{ } \\&\equiv 7139^{5} \cdot 7054 \equiv (7139^2)^{2} \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 1585 \\&\text{ } \\&\equiv 4723 \cdot 1585 \\&\text{ } \\&\equiv 2500 \ (\text{mod} \ 7919) \end{aligned}$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

Fermat’s Little Theorem and Mental Poker

Posted on July 12, 2013 by Dan Ma

In this post we demonstrate another use of the Fermat’s Little Theorem.

How can two people play poker when they are not sitting face to face from each other? If the game of poker is played over long distance (e.g. via a telephone line or some electronic communication channel), there will be a need to ensure a fair game. For example, the two players must use the same deck of cards (ensuring that there will be no duplicates). The deck of cards will need to be well shuffled. Each player cannot see the cards of the other player. One solution is to use a trusted third party to do the shuffling and selecting of cards. If a third party cannot be found or it is felt that the third party cannot be trusted to be fair, then one should consider the cryptographic solution described in this post. This soultion was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm).

___________________________________________________________________________________________________________________

Setting Up the Deck of Cards

Let’s say that the players are Andy and Becky. Since they are not using a physical deck of cards, they need to represent the cards by numbers. Let’s say that they agree to number the cards as follows:

$\displaystyle \heartsuit 2=1020 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 2=2020 \ \ \ \ \ \ \ \ \ \ \ \spadesuit 2=3020 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 2=4020$

$\displaystyle \heartsuit 3=1030 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 3=2030 \ \ \ \ \ \ \ \ \ \ \ \spadesuit 3=3030 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 3=4030$

$\displaystyle \heartsuit 4=1040 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 4=2040 \ \ \ \ \ \ \ \ \ \ \ \spadesuit 4=3040 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 4=4040$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$\displaystyle \heartsuit Q=1120 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit Q=2120 \ \ \ \ \ \ \ \ \ \ \spadesuit Q=3120 \ \ \ \ \ \ \ \ \clubsuit Q=4120$

$\displaystyle \heartsuit K=1130 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit K=2130 \ \ \ \ \ \ \ \ \ \spadesuit K=3130 \ \ \ \ \ \ \ \ \clubsuit K=4130$

$\displaystyle \heartsuit A=1140 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit A=2140 \ \ \ \ \ \ \ \ \ \ \spadesuit A=3140 \ \ \ \ \ \ \ \ \ \clubsuit A=4140$

___________________________________________________________________________________________________________________

Setting Up the Pad Locks

The card numbers need to be encrypted before they can be passed between the two players. Here’s how it works.

Both players agree to choose a large prime number $p$ . This number $p$ needs to be larger than all the card numbers and the encrypted card numbers. The larger $p$ is, the harder it will be for any one of the players to cheat.

Now each of the players needs to choose an encryption-decryption key (a padlock) that the player keeps secret. Let’s start with Andy. He chooses a pair of positive numbers $a_0$ and $a_1$ such that the following holds:

$a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1)$

Equivalently the pair $a_0$ and $a_1$ satisfies the equation $a_0 \cdot a_1=1+(p-1) \cdot k$ for some integer $k$ . The number $a_0$ will be used for locking (encryption) and the number $a_1$ will be used for unlocking (decryption). Andy will also keep this pair of numbers away from Becky.

How will Andy use this padlock? Suppose that $m$ is a number to be encrypted. To encrypt the number, Andy raises $m$ to the power of $a_0$ and then finds the remainder upon division by $p$ . He will call the remainder $f_a(m)$ . Using congruence notation, the following is the encryption function:

$f_a(m) \equiv m^{a_0} \ (\text{mod} \ p)$

If Andy needs to recover $m$ from the encrypted card number $c=f_a(m)$ , all he has to do is to raise $c$ to the power of $a_1$ and then find the remainder upon division by $p$ . Call the remainder $g_a(c)$ , which will be the original card number $m$ . Using congruence notation, the following is the decryption function:

$g_a(c) \equiv c^{a_1} \ (\text{mod} \ p)$

The decrypted number is the original number. Thus we have $g_a(c)=m$ . A proof of this relies on the Fermat’s Little Theorem (see proof).

Because the numbers involved are usually large, no one will try to raise $m$ to the power of $a_0$ and then divides by $p$ to find the remainder. Instead, Andy should use special software. If software is not available, Andy can rely on congruence modulo arithmetic, which should also be done by a computer. See below for a demonstration of the congruence modulo arithmetic.

The other player Becky also needs a padlock. Specifically, she chooses a pair of numbers $b_0$ and $b_1$ that satisfy the following:

$b_0 \cdot b_1 \equiv 1 \ (\text{mod} \ p-1)$

This pair of number serves the same purpose as the pair that belongs to Andy. Of course, $b_0$ and $b_1$ need to be kept secret from Andy. The following shows the encryption and decryption functions for Becky’s padlock.

$f_b(m) \equiv m^{b_0} \ (\text{mod} \ p)$

$g_b(c) \equiv c^{b_1} \ (\text{mod} \ p)$

___________________________________________________________________________________________________________________

How to Play the Game

Suppose the card numbers are $m_1, m_2, m_3, \cdots, m_{52}$ (the above is one example of card number assigment). Andy then encrypts the card number using his encryption function $f_a(m)$ . The following lists the encrypted card numbers.

$\displaystyle f_a(m_1),\ f_a(m_2), \ f_a(m_3),\cdots,f_a(m_{52})$

Andy then passes these encrypted card numbers to Becky. She shuffles the encrypted deck thorughly. She then chooses a 5-card hand for Andy. Becky then chooses another 5-card hand for herself. Becky uses her key to encrypt her 5-card hand. Becky passes both 5-card hands to Andy. The following shows what Becky passes to Andy.

Andy’s 5-card hand: $f_a(m_i) \equiv m_i^{a_0} \ (\text{mod} \ p)$ for 5 distinct values of $i$ .

Becky’s 5-card hand: $f_b(f_a(m_j)) \equiv f_a(m_j)^{b_0} \ (\text{mod} \ p)$ for 5 distinct values of $j$ .

Once Andy gets the two 5-card hands, he decrypts his own 5-card hand and gets back the original card numbers. He also decrypts Becky’s 5-card hand and passes that back to Becky.

Andy’s 5-card hand: $g_a(f_a(m_i)) \equiv (m_i^{a_0})^{a_1} \equiv m_i \ (\text{mod} \ p)$

Becky’s 5-card hand: $g_a(f_b(f_a(m_j))) \equiv (f_a(m_j)^{b_0})^{a_1}=(f_a(m_j)^{a_1})^{b_0} \equiv m_j^{b_0} \ (\text{mod} \ p)$ , which Andy passes back to Becky.

Once Becky’s recieves her 5-card hand back from Andy, she decrypts the cards immediately and gets back the original card numbers.

Becky’s 5-card hand: $g_b(m_j^{b_0}) \equiv (m_j^{b_0})^{b_1} \equiv m_j \ (\text{mod} \ p)$

Now each of the players has a 5-card hand that is only known to himself or herself. If they need to select new cards from the deck, they can follow the same back-and-forth procedures of encrypting and decrypting.

How fair is the poker game played in this manner? How secure is the game? It is very fair and secure if the players follow the rules and do not cheat. It is obviously possible to cheat. When Andy passes the 52 encrypted card numbers to Becky, Becky certainly can try to break Andy’s lock by figuring out Andy’s $a_0$ . When Becky passes her encrypted cards to Andy, he can try to figure out Becky’s $b_0$ . For that to happen, the player who wants to cheat will need to have enormous amount of computational resources at the ready. Thus the prime number $p$ should be large enough to make cheating an intractable problem. On the other hand, even when the prime number is of a moderate size, there has to be a fair amount of computational resources in order to play the game efficiently, with all the encrypting and decrypting that have to be done.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

We now use Fermat’s Little Theorem to show that the encryption-decryption key works correctly and accurately. We show the following:

$(m^{a_0})^{a_1} \equiv m \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

For the descriptions of the numbers $m$ , $p$ , $a_0$ and $a_1$ , see the above section Setting Up the Padlocks. First we state the Fermat’s Little Theorem.

Fermat’s Little Theorem
Let $q$ be a prime number. Then for any integer $a$ , $a^q-a$ is an integer multiple of $q$ (or $q$ divides $a^q-a$ ). Using congruence notation, the theorem can be expressed as:

$a^q \equiv a \ (\text{mod} \ q)$

If the integer $a$ is not divisible by $q$ , then we can divide out $a$ and the theorem can be expressed as:

$a^{q-1} \equiv 1 \ (\text{mod} \ q)$

For a proof and a fuller discussion of Fermat’s little theorem, see this post.

We now prove the property $(1)$ . Recall that the pair of positive integers $a_0$ and $a_1$ are keys to lock and unlock a number $m$ . They are chosen such that $a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1)$ , or equivalently $a_0 \cdot a_1=1+(p-1) \cdot k$ for some integer $k$ . This integer $k$ must be positive since $a_0$ and $a_1$ are both positive.

In the derivation below, we repeated use the fact that $m^p \equiv m \ (\text{mod} \ p)$ (applying the Fermat’s Little Theorem).

$\displaystyle \begin{aligned} m&\equiv m^p \ (\text{mod} \ p)=m \cdot m^{p-1} \\&\equiv m^p \cdot m^{p-1} \ (\text{mod} \ p)=m \cdot m^{2(p-1)} \\&\equiv m^p \cdot m^{2(p-1)} \ (\text{mod} \ p)=m \cdot m^{3(p-1)} \\&\cdots \\&\cdots \\&\cdots \\&\equiv m^p \cdot m^{(k-1)(p-1)} \ (\text{mod} \ p)=m \cdot m^{k(p-1)} \\&=m \cdot m^{k(p-1)} \equiv m^{a_0 \cdot a_1} \ (\text{mod} \ p) \end{aligned}$

___________________________________________________________________________________________________________________

Example of Congruence Calculation

For a numerical example, we use a small prime number $p=55,049$ . Though a small prime number, it is large enough to make the illustration meaningful. Andy chooses $a_0 \cdot a_1$ such that $a_0 \cdot a_1=1+(p-1) \cdot k$ for some integer $k$ . Andy decides to use $k=3817$ , leading to $a_0=2,657$ and $a_1=79,081$ .

As illustration of how the calculation is done, let $m=1020$ (the number for $\heartsuit 2$ as indicated above).

To decrypt this card, Andy needs to raise $1020$ to the 2657th power and then find the remainder upon division by $p=50,049$ . This is the definition for $1010200^{269}$ modulo $p$ . But the calculation is not easy to do directly without special software. We present here a “divide and conquer” approach that use the division algorithm in each step to reduce the exponent by half.

To start, note that $1020^2 \equiv 49518 \ (\text{mod} \ 55049)$ , meaning that the remainder is $49518$ when $1020^2$ is divided by $55049$ . In the following series of steps, a congruence calculation is performed in each step (using the division algorithm) to reduce the exponent by half.

$\displaystyle \begin{aligned} 1020^{2657}&\equiv (1020^2)^{1328} \cdot 1020 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 49518^{1328} \cdot 1020 \equiv (49518^2)^{664} \cdot 1020 \\&\text{ } \\& \equiv 39766^{664} \cdot 1020 \equiv (39766^2)^{332} \cdot 1020 \\&\text{ } \\& \equiv 52231^{332} \cdot 1020 \equiv (52231^2)^{166} \cdot 1020 \\&\text{ } \\&\equiv 14068^{166} \cdot 1020 \equiv (14068^2)^{83} \cdot 1020 \\&\text{ } \\& \equiv 7469^{83} \cdot 1020 \equiv (7469^2)^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\& \equiv 21324^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\&\equiv 21324^{41} \cdot 21618 \equiv (21324^2)^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\& \equiv 8236^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\& \equiv 8236^{20} \cdot 1906 \equiv (8236^2)^{10} \cdot 1906 \\&\text{ } \\& \equiv 11328^{10} \cdot 1906 \equiv (11328^2)^{5} \cdot 1906 \\&\text{ } \\& \equiv 4365^5 \cdot 1906 \equiv (4365^2)^2 \cdot 4365 \cdot 1906 \\&\text{ } \\& \equiv 6271^2 \cdot 4365 \cdot 1906 \\&\text{ } \\&\equiv 6271^2 \cdot 7291 \\&\text{ } \\&\equiv 20455 \cdot 7291 \\&\text{ } \\&\equiv 9664 \ (\text{mod} \ 55049) \end{aligned}$

Thus the card number $1020$ is encrypted as $9664$ . To recover the original card number from this encrypted number, Andy needs to raise $9664$ to the power of $a_1=79081$ . Here, we get an assist from Fermat’s Little Theorem in addition to the ‘divide and conquer” congruence arithmetic that is used above.

According to Fermat’s Little Theorem, $9664^{55048} \equiv 1 \ (\text{mod} \ 55049)$ . Thus we have

$9664^{79081} \equiv 9664^{55048} \cdot 9664^{24033} \equiv 9664^{24033} \ (\text{mod} \ 55049)$

With the help of Fermat’s Little Theorem, the exponent $79081$ has come down to $24033$ . In the rest of the way, the “divide and conquer” approach is used.

$\displaystyle \begin{aligned} 9664^{24033}&\equiv (9664^2)^{12016} \cdot 9664 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 29782^{12016} \cdot 9664 \equiv (29782^2)^{6008} \cdot 9664 \\&\text{ } \\&\equiv 8237^{6008} \cdot 9664 \equiv (8237^2)^{3004} \cdot 9664 \\&\text{ } \\&\equiv 27801^{3004} \cdot 9664 \equiv (27801^2)^{1502} \cdot 9664 \\&\text{ } \\&\equiv 7641^{1502} \cdot 9664 \equiv (7641^2)^{751} \cdot 9664 \\&\text{ } \\&\equiv 32941^{751} \cdot 9664 \equiv (32941^2)^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 48506 \equiv (38642^2)^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 5451 \equiv (39^2)^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 47442 \equiv (1521^2)^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv 1383^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv 1383^{46} \cdot 45092 \equiv (1383^2)^{23} \cdot 45092 \\&\text{ } \\&\equiv 41023^{23} \cdot 45092 \equiv (41023^2)^{11} \cdot 41023 \cdot 45092 \\&\text{ } \\&\equiv 38599^{11} \cdot 41023 \cdot 45092 \\&\text{ } \\&\equiv 38599^{11} \cdot 52618 \equiv (38599^2)^{5} \cdot 38599 \cdot 52618 \\&\text{ } \\&\equiv 36665^5 \cdot 38599 \cdot 52618 \\&\text{ } \\&\equiv 36665^5 \cdot 24376 \equiv (36665^2)^{2} \cdot 36665 \cdot 24376 \\&\text{ } \\&\equiv 25645^2 \cdot 36665 \cdot 24376 \\&\text{ } \\&\equiv 25645^2 \cdot 25525 \\&\text{ } \\&\equiv 50671 \cdot 25525 \\&\text{ } \\&\equiv 1020 \ (\text{mod} \ 55049) \end{aligned}$

In each step of the above calculation, the division algorithm is applied to reduce the exponent by half. For example, to go from the first line to the second line, $9664^2$ is divided by $55049$ to obtain the remainder $29782$ , i.e. $9664^2 \equiv 29782 \ (\text{mod} \ 55049)$ . The number $1020$ in the last line is the remainder when $50671 \cdot 25525$ is divided by $55049$ .

___________________________________________________________________________________________________________________

Fermat’s Little Theorem and RSA Algorithm

Posted on July 8, 2013 by Dan Ma

RSA is a cryptographic algorithm that is used to send and receive messages. We use the Fermat’s Little Theorem to prove that RSA works correctly and accurately. In other words, the decrypted message is indeed the original message from the sender. Mathematically we show that applying the encryption function and the decryption function successively produces the identity function.

To see how RSA works, see the previous post An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

RSA Algorithm

We first briefly describe the algorithm and then present the mathematical statement to validate.

Let $N=p \cdot q$ where $p$ and $q$ are two prime numbers. Let $\phi=(p-1) \cdot (q-1)$ . Choose an integer $e$ with $1<e<N$ such that $e$ and $\phi$ are relatively prime.

The public key consists of $N$ and $e$ where $e$ is the encryption key. Once it is published, anyone can use it to encrypt messages to send to the creator of the public key. The following is the encryption function:

$f(M) \equiv M^e \ (\text{mod} \ N)$

where $M$ is a positive integer and is the original message.

The private key is a positive integer $d$ that satisfies:

$d \cdot e \equiv 1 \ (\text{mod} \ \phi=(p-1) \cdot (q-1))$

In other words, $d$ is the multiplicative inverse of $e$ in the modular arithmetic of modulo $\phi$ . The above condition is equivalent to: $de-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$ .

The number $d$ is the decryption key that will be used to decode messages. So it should remain private.

Once the creator of the public key receives an encrypted message $C=f(M)$ , he or she uses the following decryption function to obtain the original message $M$ .

$g(C) \equiv C^d \ (\text{mod} \ N)$

___________________________________________________________________________________________________________________

The Mathematical Statement to Validate

What we prove is that the decryption function is to undo the encryption function. Specifically, we prove the following:

$g(C)=g(f(M))=(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

In other words, applying the decryption function $g$ to the encryption function $f$ produces the original message.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

In this section, we list out the tools we need to prove the correctness of RSA.

Theorem 1 (Fermat’s Little Theorem)
If $p$ is a prime number and $a$ is an integer such that $a$ and $p$ are relatively prime, then

$a^{p-1}-1$ is an integer multiple of $p$

or equivalently $a^{p-1} \equiv 1 \ (\text{mod} \ p)$ .

For a proof of Fermat’s little theorem, see this post.

Lemma 2 (Euclid’s Lemma)
Let $a$ , $b$ and $d$ be integers where $d \ne 0$ . Then if $d$ divides $a \cdot b$ (symbolically $d \lvert a \cdot b$ ), then either $d \lvert a$ or $d \lvert b$ .

Euclid’s Lemma is needed to prove the following Lemma.

Lemma 3
Let $M$ be an integer. Let $p$ and $q$ be prime numbers with $p \ne q$ .

Then if $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$ , then $a \equiv M \ (\text{mod} \ p \cdot q)$ .

Proof of Lemma 3
Suppose we have $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$ . Then for some integers $i$ and $j$ , we have:

$a=M+p \cdot i$ and $a=M+q \cdot j$ .

Then $p \cdot i=q \cdot j$ . This implies that $p$ divides $q \cdot j$ ( $p \lvert q \cdot j$ ). By Euclid’s lemma, we have either $p \lvert q$ or $p \lvert j$ . Since $p$ and $q$ are distinct prime numbers, we cannot have $p \lvert q$ . So we have $p \lvert j$ and that $j=p \cdot w$ for some integer $w$ .

Now, $a=M+q \cdot j=M+q \cdot p \cdot w$ , implying that $a \equiv M \ (\text{mod} \ p \cdot q)$ . $\blacksquare$

___________________________________________________________________________________________________________________

The Proof of (1)

We now prove the property $(1)$ described above. We show that

$(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$

We first show that $M^{ed} \equiv M \ (\text{Mod} \ p)$ and $M^{ed} \equiv M \ (\text{Mod} \ q)$ . Then the desired result follows from Lemma 3.

To show $M^{ed} \equiv M \ (\text{Mod} \ p)$ , we consider two cases: $M \equiv 0 \ (\text{Mod} \ p)$ or $M \not \equiv 0 \ (\text{Mod} \ p)$ .

Case 1. $M \equiv 0 \ (\text{Mod} \ p)$ . Then $M$ is an integer multiple of $p$ , say $M=p \cdot w$ where $w$ is an integer. Then $M^{ed}=(p \cdot w)^{ed}=p \cdot p^{ed-1} \cdot w^{ed}$ . So both $M$ and $M^{ed}$ are integer multiples of $p$ . Thus $M^{ed} \equiv M \ (\text{Mod} \ p)$ .

Case 2. $M \not \equiv 0 \ (\text{Mod} \ p)$ . This means that $p$ and $M$ are relatively prime (having no common divisor other than 1). Thus we can use Fermat’s Little Theorem. We have $M^{p-1} \equiv 1 \ (\text{mod} \ p)$ .

From the way the decryption key $d$ is defined above, we have $ed-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$ . We then have:

$\displaystyle \begin{aligned} M^{ed}&=M^{ed-1} \cdot M \\&=M^{(p-1) \cdot (q-1) \cdot k} \cdot M \\&=(M^{p-1})^{(q-1) \cdot k} \cdot M \\&\equiv (1)^{(q-1) \cdot k} \cdot M \ (\text{Mod} \ p) \ * \\&\equiv M \ (\text{Mod} \ p) \end{aligned}$

At the step with *, we apply Fermat’s Little Theorem. So we have $M^{ed} \equiv M \ (\text{Mod} \ p)$ .

The same reason reasoning can show that $M^{ed} \equiv M \ (\text{Mod} \ q)$ .

By Lemma 3, it follows that $M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$ . $\blacksquare$

___________________________________________________________________________________________________________________

Revised August 9, 2014.

An Illustration of the RSA Algorithm

Posted on July 7, 2013 by Dan Ma

The following 617-digit number (all 617 digits starting with $251$ and ending in $357$ ) is a product of two prime numbers $p$ and $q$ . How long will it take to find these two prime factors?

The above number is a challenge to the public to come up with the two prime factors (see RSA challenge number and RSA factoring challenge). No one has been able to successfully meet the challenge. In fact, even with the current state of the art in supercomputing technology, it could take millions of years to factor a number as big as the one shown above. According to the organization that posed the challenge (RSA Laboratories), barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come.

RSA is a cryptographic algorithm that is used to send and receive sensitive data. The name RSA stands for the last names of the creators of the algorithm – Ron Rivest, Adi Shamir and Leonard Adleman.

The algorithm uses a pair of large prime numbers in setting up a public key to encrypt and a private key to decrypt data. The public key is known to the public and includes a large integer $N$ (such as the one indicated at the beginning of the post) that is a product of two prime numbers $p$ and $q$ . The private key is computed using two prime factors $p$ and $q$ and is needed to decrypt the messages encrypted by the public key. The RSA scheme is built on the monumental difficulty in factoring large numbers. Barring some system vulnerability that hackers can exploit, it is all but certain that messages sent via RSA scheme can only be read by the intended party – the legitimate party that possesses the private key.

This post gives an illustration of how the RSA algorithm work using much smaller prime numbers. The RSA algorithm is also an application of the Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

The example given below makes use of congruence arithmetic. If $a$ , $b$ and $m$ are integers, the symbol $a \equiv b \ (\text{mod } m)$ means that the difference $a-b$ is divisible by $m$ (we say that $a$ is congruent to $b$ modulo $m$ ). For example, $15 \equiv 3 \ (\text{mod } 12)$ (in terms of clock arithmetic, 6 hours after 9 o’clock is not 15th o’clock but is 3 o’clock). For more information about congruence relation and congruence arithmetic, see this blog post or this Wikipedia entry.

___________________________________________________________________________________________________________________

Example of RSA

The example uses small prime numbers to make the illustration easy to follow. The example has the following steps:

Andy creates a public key and a private key. He gives the public key to Becky and keeps the private key to himself.
Becky then uses the public key to encrypt a message and sends it to Andy.
Andy then uses the private key to decrypt the message received from Becky.

$\text{ }$

______________________________________________________
Step 1 – Generating the Public Key and Private Key

Choose two prime numbers $p$ and $q$ . In this example, let $p=29$ and $q=47$ . Then calculate the following numbers:

$N=p \times q=1363$

$(p-1) \times (q-1)=1288$

Choose an integer $e$ with $1<e<N$ such that $e$ and $(p-1) \times (q-1)$ are relatively prime (meaning the only common divisor is 1). For this example, Andy chooses $e=11$ .

The public key consists of $N=1363$ and $e=11$ , which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy (see Step 2 below). The number $e$ is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number $d$ such that:

$e \cdot d \equiv 1 \ (\text{mod } (p-1) \cdot (q-1))$

In this example, find the number $d$ such that

$11 \cdot d \equiv 1 \ (\text{mod } 1288)$

Specifically, we need to find the number $d$ that satisfies $11d=1+1288 k$ for some integer $k$ . When $k=10$ , we have a solution $d=1171$ .

The number $d=1171$ will be used to decrypt any message that will come from Becky. So Andy needs to keep $d$ private and secure.

______________________________________________________
Step 2 – Encrypting a Message using the Public Key

Becky wishes to send a message $T$ (in text) to Andy. Becky first translates $T$ into an integer $M$ (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message $M$ back to the text message $T$ . Note that the mapping for translating letters into numbers and back is not part of the RSA algorithm, which only encrypts and decrypts numeric messages.

Suppose the message is $M=289$ . The following is the encryption function – the function that generates the encrypted message $C$

$f(M) \equiv M^e \ (\text{mod } N)$

In this example, the encryption function is:

$f(M) \equiv 289^{11} \ (\text{mod } 1363)$

The encrypted message is the number $C=f(M)$ is the remainder that is obtained when $289^{11}$ is divided by $N=1363$ . This can be done in a process using congruence arithemtic that can be described as “divide and conquer”. The process is to reduce the exponent by half in each step of the step by step approach.

First, note that $289^2 \equiv 378 \ (\text{mod} \ 1363)$ since $378$ is the remainder when $289^2$ is divided by $1363$ (i.e. division algorithm). Then use the division algorithm successively as shown in the following:

$\displaystyle \begin{aligned} 289^{11}&\equiv (289^2)^5 \cdot 289 \ (\text{mod} \ 1363) \\&\text{ } \\&\equiv 378^5 \cdot 289 \equiv (378^2)^2 \cdot 378 \cdot 289 \\&\text{ } \\& \equiv 1132^2 \cdot 378 \cdot 289 \\&\text{ } \\&\equiv 1132^2 \cdot 202 \\&\text{ } \\&\equiv 204 \cdot 202 \\&\text{ } \\&\equiv 318 \ (\text{mod} \ 1363) \end{aligned}$

In the “divide and conquer” approach, a congruence calculation in done in each step to reduce the exponent (applying the division algorithm). For example, to go from the first line to the second line, the remainder $378$ is obtained when $289^2$ is divided by $1363$ . The number $318$ is the remainder when $204 \cdot 202$ is divided by $1363$ .

______________________________________________________
Step 3 – Decrypting the Message Receiving from Becky

Andy receives the encrypted message $C=318$ . To decrypt $C$ , the private key $d$ that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message $M$ .

$g(C) \equiv C^d \ (\text{mod } N)$

In particular, Any needs to find the number $M=g(C)$ that satisfies the following:

$g(C) \equiv 318^{1171} \ (\text{mod } 1363)$

The decrypted message $M=g(C)$ is the remainder when $318^{1171}$ is divided by $1363$ . A “divide and conquer” approach can be used.

$\displaystyle \begin{aligned} 318^{1171}&\equiv (318^2)^{585} \cdot 318 \ (\text{mod} \ 1363) \\&\text{ } \\&\equiv 262^{585} \cdot 318 \equiv (262^2)^{292} \cdot 262 \cdot 318 \\&\text{ } \\& \equiv 494^{292} \cdot 262 \cdot 318 \\&\text{ } \\&\equiv 494^{292} \cdot 173 \equiv (494^2)^{146} \cdot 173 \\&\text{ } \\& \equiv 59^{146} \cdot 173 \equiv (59^2)^{73} \cdot 173 \\&\text{ } \\& \equiv 755^{73} \cdot 173 \equiv (755^2)^{36} \cdot 755 \cdot 173 \\&\text{ } \\& \equiv 291^{36} \cdot 755 \cdot 173 \\&\text{ } \\&\equiv 291^{36} \cdot 1130 \equiv (291^2)^{18} \cdot 1130 \\&\text{ } \\& \equiv 175^{18} \cdot 1130 \equiv (175^2)^{9} \cdot 1130 \\&\text{ } \\& \equiv 639^{9} \cdot 1130 \equiv (639^2)^{4} \cdot 639 \cdot 1130 \\&\text{ } \\& \equiv 784^{4} \cdot 639 \cdot 1130 \\&\text{ } \\&\equiv 784^{4} \cdot 1043 \equiv (784^2)^{2} \cdot 1043 \\&\text{ } \\& \equiv 1306^{2} \cdot 1043 \\&\text{ } \\&\equiv 523 \cdot 1043 \\&\text{ } \\&\equiv 289 \ (\text{mod} \ 1363) \end{aligned}$

We just illustrates how Andy decrypts Becky’s message of $C=318$ to find the original message of $M=289$ . The calculation is tedious if done manually but is simple for a computer.

___________________________________________________________________________________________________________________

Summary

We summarize the main steps in the above example.

______________________________________________________
Step 1 – Generating the Public Key and Private Key

Choose two prime numbers $p$ and $q$ . Then calculate the following numbers:

$N=p \times q$

$(p-1) \times (q-1)$

Choose an integer $e$ with $1<e<N$ such that $e$ and $(p-1) \times (q-1)$ are relatively prime (meaning the only common divisor is 1).

The public key consists of $N$ and $e$ , which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy. The number $e$ is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number $d$ such that:

$e \cdot d \equiv 1 \ (\text{mod } (p-1) \cdot (q-1))$

The number $d$ is the decryption key and will be used to decrypt any message that will come from Becky. So Andy needs to keep $d$ private and secure.

______________________________________________________
Step 2 – Encrypting a Message using the Public Key

The following is the encryption function – the function that generates the encrypted message $C$ .

$f(M) \equiv M^e \ (\text{mod } N)$

The encrypted message that Becky will send to Andy is $C=f(M)$ .

______________________________________________________
Step 3 – Decrypting the Message Receiving from Becky

Andy receives the encrypted message $C$ . To decrypt $C$ , the private key $d$ that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message $M$ .

$g(C) \equiv C^d \ (\text{mod } N)$

The original message sent from Becky is $M=g(C)$ .

Note that $M=g(f(M))$ . Thus the function $f$ is the inverse function of $g$ (and vice versa). This fact can be established by using Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).