January 1, 0001

An overview of modular arithmetic and relations

What’s the big deal about modular aritmetic you may ask? Well, it’s basically the precursor to number theory, which is a cornerstone of cryptography. This post is an attempt to lay all of it out in a simple way for you to understand.

Divisibility

Let’s take two integers: a and b. Now let’s introduce a new integer called m so that b=a*m.

Simple right? We can actually express this relation in a few ways:

- b is a multiple of a
- b is divisible by a
- a is a divisor of b
- a is a factor of b

We can express this relation via the following notation: a | b > a is a divisor/factor of b.

There’s actually some pretty interesting implications of this. For example: - If a | b then a | bc. - If a is a factor ofb, then it’ll be the factor of b no matter what b multiplied with.

Prime Numbers

As you may remember from school, a prime number is such that it can only be divided by itself. The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

If we wanted to find the prime factors of 345 we could do the following: - 3 * 115 = 3 * 5 * 23 - 5 * 69 = 5 * 2 * 23

So how can we quickly check whether a number is prime or not without having to list all the factors.

comments powered by Disqus