Modular Arithmetic

Modular Arithmetic

Niven Achenjang bio photo By Niven Achenjang Comment

I plan on writing a couple posts related to cryptography soon. Before I do that, I wanted to have a post covering some of the basics of modular arithmetic first, because this material will be needed for the cryptographic posts.

Divisibility


The first thing to know is that modular arithmetic is all about integers. We do not care about rationals, reals, or anything else, only integers 1. As such, all our definitions have to be written in terms of integers, and the first such definition is that of divisibility. It is tempting to say that divides iff is an integer, but writing means we are entering the realm of rationals, which we cannot do. Therefore, we instead say that divides iff there exists an integer such that . This way we are defining divisibility in terms of multiplication (which is defined for integers) instead of division (which is not defined for integers in general). We write when divides . The following are a few properties of divisibility.

Mod


In the previous section I said that division was not defined for integers in general. That was a bit of a lie. It is, just not in the way we normally think of division.

Division algorithm:
For any two integers and , there exists a unique pair of integers and such that . We call the dividend, the divisor the quotient, and the remainder.

From this theorem, we get the following definition.

Definition of :
If where , then we say that .

In other words, is the remainder when is divided by . Mod has some nice properties, such as

These properties motivate the following definition.

Definition of :
We write iff . We read this as “ is congruent to modulo ”.

Note that the above definition is equivalent to saying that iff 2. It is easy to see that this new form of mod inherits some nice properties from the one we first introduced. Namely,

Finally, note that for all , there exits a in such that . This is because . This realization motivates the following definition.

Definition of :
3

Euclidean Algorithm


We begin this section with a definition or two.

A few definitions:
We call the greatest common divisor of and if , , and no larger integer divdes both and . We write to denote that is the greatest common divisor of and .
We say that and are coprime (or relatively prime) if they have no common divisors other than . Equivalently, and are coprime iff .

We will see some of the uses of these concepts later in this post, but first, it would be nice if we had a way of calculating the greatest common divisior of two numbers. We could check each number that was less than them and find the largest one that divides both of them that way, but that would be time consuming. For a faster method, we use the Euclidean Algorithm.

The idea is to define a sequence of numbers such that . To do this, we start with and where 4. We then define subsequent ’s by division: . In other words, . We keep doing this until we finally reach . Our answer is then . This algorithm can be implemented in (python) code as follows:

def gcd(a,b):
	if abs(b) > abs(a):
		return gcd(abs(b),abs(a))
	elif b==0:
		return abs(a)
	else:
		return gcd(b,a%b)

To finish this section, let’s calculate the greatest common divisor of and .

Therefore, .

Analyzing the Euclidean Algorithm


This section will not be needed to understand the rest of this post and can be skipped. In it, we will discuss the Euclidean Algorithm slightly more formally, proving that it gives the correct answer and does so “quickly”.

Theorem 1:
For any and , the Euclidean Algorithm terminates.

Pf: Let and be any integers 5 where, without loss of generality, . Then, we claim that the sequence of remainders in the Euclidean Algorithm – – is finite. First, since for , we know that for . Second, , so . Therefore, the ’s form a strictly decreasing (in magnitude) sequence of integers greater than or equal to for . Thus, there must be finitely many ’s. Else, the sequence would eventually be less than , a contradiction.

Theorem 2:
For any and , the Euclidean Algorithm gives the correct value.

Pf: Let and be any integers, and let be the sequence of remainders attained from the Euclidean Algorithm. Then, we claim that . To see this, first note that for all and so . We proceed to prove our claim by showing that for all . Recall that . Let be any common divisor of and . Then, divides , so is a common divisor of and . Similarily, if is a common divisor of and , then also divides . As such, the common divisors of and are exactly the common divisors of and . Namely, . It follows by induction that .

Lemma 1:
Given and where , let be the sequence of remainders attained from the Euclidean Algorithm. Then, for all .

Pf: We proceed with a proof by contradiction. Suppose that for some , . Then, we have and . Since and , we know that , so . However, since and , , which is impossible. Therefore, there must not exist a with . In other words, for all , .

Theorem 3:
Given and where , let be the sequence of remainders attained from the Euclidean Algorithm. Then, .

Pf: Let and note that, by the preceeding lemma, . Therefore, . It follows from this that .

Division


One thing that may be surprising to hear is that modular arithmetic allows for division (sometimes). The division problem is as follows. Given and , find a such that . We will simply take for granted the fact that such a exits iff and are coprime and that such a is unique (up to modular congruence) when it does exits. Furthermore, without going in to the details here, I will mention that and be computed from and using the Extended Euclidean Algorithm or Fermat’s Little Theorem. If exists, then we call it the inverse of . Motivated by the fact that the inverse of exists only when is coprime to , we present the following definition.

Defintion of :
is the set of all numbers less than or equal to that are coprime to . This set is sometimes referred to as .

Fermat’s Little Theorem


Fermat’s Little Theorem:
If is a prime number, then for any integer . Furthermore, if is not divisible by , then .

This theorem is stated here without proof. The vigilent reader 6 will notice that if is prime then all have an inverse and that this inverse is .

Euler’s Totient Function


Euler’s Totient Function, also known as Euler’s phi Function, is a function . is defined as the number of integers less than or equal to that are coprime to . So, . The following theorem’s involving Euler’s Totient Function are presented without proof.

Theorem 4:
If for prime , then .

Theorem 5:
if and are coprime.

Theorem 6:
If is coprime to , then .

  1. Unless otherwise stated, assume any variable written in this post can only have an integer value. 

  2. This definition was also motivated by the desire to write mod less frequently. 

  3. For those of you with some familiarity in algebra, this is a group under addition for all n and field under addition and multiplication when n is prime. 

  4. If b is bigger than a, then simply swap a and b. 

  5. Probably should have mentioned this earlier. When a and b are negative, we make use of the fact that gcd(a,b)=gcd(|a|,|b|) and compute their gcd that way. 

  6. The truly vigilant reader will notice that I misspelled vigilant. 

comments powered by Disqus