By Camille Clark, Layke Jones, Isabella Lane, Aza McFadden*, and Lizbeth Otero.

*Aza helped the group work through the problem set but was unfortunately unable to attend camp during the blog writing.

Cryptography is a field of coding and decoding information. It relies on the framework of number theory. Therefore, it can be used to connect theories as well as teaching others the fundamental properties of integers. Relevant number theory topics are modular arithmetic, prime factorization, greatest common divisor, and theorems such as the Chinese Remainder Theorem and Euler’s Theorem. This blog post will focus on the first three topics.

Modular Arithmetic

Modular arithmetic is a system of arithmetic used for integers. For modular arithmetic, you have to apply what you already know about division to find the remainder.
For integers such as n and d, there are unique integers like q and r for which n = q*d + r.
The dividend, in this case, would be n, so d would be the divisor, q the quotient and r the remainder.

For example:
29 = 2*13 +3
5 = 1*3 + 2.

 

Prime factorization

Let’s start off with the definitions of prime, composite numbers, and factorization.

A prime number is an integer that has two factors that can only be 1 and itself. By convention, 1 is not a prime number.

A composite number is an integer that can evenly be divided by numbers other than 1 and itself.

Factors are the numbers you multiply together to get a number. Like 2 and 3 are factors of 6.

Lastly, prime factorization is the process of writing integers as products of prime numbers. It can be done with the following algorithm, here shown for the factorization of 12:

12 / 2 = 6  —  6 is not a prime factor, so let’s try dividing it by 2

6 / 2 = 3  —  3 is a prime factor, so we divide by 3

12 = 2*2*3  or  12 = (2^2)*3.

Greatest common divisor

A common divisor is an integer that all the numbers in a given set can be divided into without a remainder. To calculate the gcd of 2 numbers, you need to write out the prime factorization.

For example, let’s consider 8 and 12. The prime factorization of 8 is 2^3, while the prime factorization of 12 is 3*(2^2). Then, take the largest factor that overlaps in the two factorizations. Here, 2^2 is the largest factor in common between the prime factorizations of 8 and 12; then, 4 = gcd(8,12).

We say that two integers a and b are relatively prime if gcd(a,b) = 1, where a and b don’t need to be prime themselves. For example, if a = 35 and b = 8, then gcd(a,b) = 1, but neither is a prime.