Basic Number Theory

Just to start this article off, I'd like to explain that integer refers to any number that has no trailing decimal (e.g. 2). Secondly, the modular operator refers to a division computation that leaves no remainder such as an even number (e.g. 10 ÷ 2). Lastly, any number placed after the caret (^) symbol refers to 'power of,' and the underscore (_) symbol refers to subscript.

Suppose we have two positive integers n and a. Dividing a by n will produce a quotient which is q and a remainder r that abides by the following rules:

a = qn + r where 0 <= r < n; q = [a ÷ n]

The remainder r is often referred to as a residue. For example:

```
a = 11;	n = 7;	11 = 1 × 7 + 4;		r = 4

a = -11;  n = 7;   -11 = (-2) × 7 + 3;	r = 3
```

If a is an integer and n is a positive integer, we define a mod n to be the remainder when a is divided by n which means for any integer a, we can always write:

    a = [a ÷ n] × n + (a mod n);   a mod n = r

    11 mod 7 = 4;   -11 mod 7 = 3

The modular expression has the following laws:

Commutative Laws:

    (a + b) mod n = (b + a) mod n
    (a × b) mod n = (b × a) mod n

Associative Laws:

    [(a + b) + c] mod n = [a + (b + c)] mod n
    [(a × b) x c] mod n = [a × (b × c)] mod n

Distributive law Identities:

    [a × (b × c)] mod n = [(a × b)(a × c)] mod n
    (0 + a) mod n = a mod n; (1 × a) mod n = a mod n

Two integers a and b are congruent modulo n if (a mod n) = (b mod n). This is written a ☰ b mod n. For example: 73 mod 23 = 4 and 4 mod 23 = 4 means that:

73 ☰ 4 mod 23; and 23 ☰ -9 mod 10

Note that if a ☰ 0 mod n, then n | a. The congruent modulo operator has the following properties:

1. a ☰ b mod n if n | (a - b)
2. (a mod n) = (b mod n) implies a ☰ b mod n
3. a ☰ b mod n implies b ☰ a mod n
4. a ☰ b mod n and b ☰ c mod n

To demonstrate the first point, if n | (a - b ) then (a - b) = kn for some k, so we can write a = b + kn. Therefore, (a mod n) = (remainder when b + kn is divided by n) = (remainder when b is divided by n) = (b mod n).

• 23 ☰ 8 (mod 5) because 23 - 8 = 15 = 5 × 3
• -11 ☰ 5 (mod 8) because -11 - 5 = -16 = 8 × -2
• 81 ☰ 0 (mod 27) because 81 - 0 = 81 = 27 × 3

Modular Arithmetic Operations

Modular arithmetic is defined by these properties:

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) - (b mod n)] mod n = (a - b) mod n
3. [(a mod n) x (b mod n)] mod n = (a × b) mod n

The remaining properties can be easily proved. Here are examples of the three properties:

     11 mod 8 = 3;		15 mod 8 = 7
     [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2
     (11 + 15) mod 8 = 26 mod 8 = 2
     [(11 mod 8) - (15 mod 8)] mod 8 = -4 mod 8 = 4
     (11 - 15) mod 8 = -4 mod 8 = 4
     [(11 mod 8) × (15 mod 8)] mod 8 = 21 mod 8 = 5
     (11 × 15) mod 8 = 165 mod 8 = 5

Exponentiation, or 'to the power of' is performed by repeated multiplication, just like in ordinary arithmetic. To find 11^7 mod 13, we can proceed as follows:

    11^2 = 121 ☰ 4 mod 13
    11^4 ☰ 4^2 ☰ 3 mod 13
    11^7 ☰ 11 × 4 × 3 ☰ 132 ☰ 2 mod 13 

As a result, the rules in ordinary arithmetic for addition, subtraction, and multiplication apply to modular arithmetic.

The following tables provide an illustration of modular addition and multiplication modulo 8. Looking at addition, the results are straightforward and there is a regular pattern to the matrix. Also, as in ordinary addition, there is an additive inverse, or negative, to each number in modular arithmetic. In this case, the negative of a number x is the number y such that x + y ☰ 0 mod 8. To find the additive inverse of a number in the left-hand column, scan across the corresponding row of the matrix to find the value 0; the number at the top of that column is the additive inverse; thus 2 + 6 = 0 mod 8.

Similarly, the entries in the multiplication table are straightforward. In ordinary arithmetic, there is a multiplicative inverse, or reciprocal, to each number. In modular arithmetic mod 8, the multiplicative inverse of x is the number y such that x × y ☰ 1 mod 8. Now, for us to find the multiplicative inverse of a number from the multiplication table, scan across the matrix in the row for that number to find the value 1. The number at the top of that column is multiplicative. Therefore, 3 × 3 = 1 mod 8. Note that not all numbers mod 8 have a multiplicative inverse.

Addition modulo 8

Multiplication modulo 8

Additive and multiplicative inverses modulo 7

Modular Exponentiation

Suppose we want to calculate 2^1234 (mod 789). If we first compute 2^1234, then reduce mod 789 we'll be working with very large numbers, even though the final answer has only 3 digits. We should therefore perform each multiplication and then calculate the remainder. Calculating the consecutive powers of 2 would require that we perform the modular multiplication 1233 times which is too slow to be practical, especially when the power becomes very large. A more efficient way would be:

To start with 2^2 ☰ 4 (mod 789) and repeatedly square both sides to get the following congruences:

    2^4   ☰ 4^2   ☰    16
    2^8   ☰ 16^2    ☰    256
    2^16    ☰ 256^2     ☰    49
    2^32    ☰ 34
    2^64    ☰ 367
    2^128     ☰ 559
    2^256     ☰ 37
    2^512     ☰ 580
    2^1024      ☰ 286

Since 1234 = 1024 + 128 + 64 + 16 + 2 (this just means that 1234 equals 10011010010 in binary), we have

2^1234 ☰ 286 × 559 × 367 × 49 × 4 ☰ 481 (mod 789)

Basic Principles

If the greatest common denominator = 1, then 1 ☰ a^Φ(n) (mod n). Note that when n = p is prime, Euler’s theorem is the same as Fermat’s theorem.

Let a, n, x, y be integers with n ≥ 1 and the gcd of a & n = 1. If x ≡ y (mod Φ(n)), then a^x ≡ a^y (mod n). In other words, if you want to work mod n, you should work mod Φ(n) in the exponent.

This is an extremely important fact that is useful in many of the following subheadings.

Fermat's Little Theorem and Euler's Theorem

Two of the most basic results in number theory are Fermat’s Little Theorems. Originally admired for their theoretical value, they have more recently proved to have important cryptographic applications.

Fermat's Little Theorem: If p is a prime and p does not divide a, then

a^p-1^ ☰ 1 (mod p).

Example: 2^10 = 1024 ☰ 1 (mod 11). We can proceed to evaluate 2^53 (mod 11): write 2^53 = (2^10)^5 2^3 ☰ 8 (mod 11). You will notice that when working with mod 11, we are essentially working with the exponents mod 10, not mod 11. In other words, from 53 ☰ 3 (mod 10), we reach the conclusion that 2^53 ☰ 2^3 (mod 11).

Usually, if 2^n-1 ☰ 1 (mod n), then the number n is prime. However, there are expectations such as 561 = 3 × 11 × 17 should be composite but 2^560 ☰ 1 (mod 561). We can then conclude that 2 ^560 ☰ 1 (mod 11) and 2^560 ☰ 1 (mod 17). If we combine it all together using the Chinese Remainder Theorem, we find that 2^560 ☰ 1 (mod 561).

Another expectation is 1729 = 7 × 13 × 19. These expectations are rare in practice.

We will also need the analog of Fermat's theorem for a composite modulus n. Let Φ(n), pronounced 'phi', be equal to the number of integers 1 <= a <= n such that the gcd(a, n) = 1. For example, if n = 10 then there are 4 integers which are 1, 3, 7, and 9. As a result, Φ(10) = 4. Φ is often called Euler's Φ-Function.

Euler's Totient Function

Before discussing Euler’s theorem, we need to introduce an important quantity in number theory, referred to as Euler’s totient function and written Φ(n), where Φ(n) is the number of positive integers less than n and relatively prime to n.

It should be clear that for a prime number p,

Φ(p) = p -1

Now suppose that we have two prime numbers p and q. then, for n = pq,

Φ(n) = Φ(pq) = Φ(p) × Φ(q) = (p-1) × (q-1)

Same values of Euler’s Totient Function Φ(n)

For a prime 'p' in particular

Φ(p) = p-1

Example:

        Φ(10 = (2-1) (5-1) = 4

        Φ(120) = 120(1-1 ÷ 2)(1-1 ÷ 3)(1-1 ÷ 5) = 32

Example 2: Compute 2^43210 (mod 101) Solution: From Fermat's theorem, we know that 2^100 ☰ 1 (mod 101). Therefore,

243210 ≡ (2100)432 210 ≡ 1432 210 ≡ 1024 ≡ 14 (mod 101)

In this case, we were able to change the exponent 43210 to 10 because 43210 ≡ 10 (mod 100)

Primitive Roots

Let's consider the powers of 3 (mod 7):

3^1 ≡ 3, 3^2 ≡ 2, 3^3 ≡ 6, 3^4 ≡ 4, 3^5 ≡ 5, 3^6 ≡ 1

Note that we obtain all the nonzero congruence classes mod 7 as powers of 3. This means that 3 is a primitive root mod 7. The following summarizes the main facts we need about primitive roots.

Proposition: Let g be a primitive root for the prime p.

1. if n is an integer, then g^n ≡ 1 (mod p) if and only if n ≡ 0 (mod p-1).
2. if j and k are integers, then g^j ≡ g^k (mod p) if and only if j ≡ k (mod p-1).

When p is prime, it is always possible to choose a so that a, a^2, a^3,.......,a^p-1 (all modula p) run through the values 1, 2, 3,.......,p-1 in some order. Such that a is called a generator or a primitive root of unity. It turns out that for each prime p there is at least one generator that proves the following theorem to be true.

If a and n are relatively prime, then there is at least one integer m that satisfies the equation below namely, m = Φ(n). The least positive exponent m for which equation a^m ≡ 1 mod n holds is referred to as the exponent to which a belongs to (mod n). Let's consider the powers of 7, modulo 19:

        7^1 = 7 mod 19
        7^2 = 49 = 2 × 19 + 11 = 11 mod 19
        7^3 = 343 = 18 × 19 + 1 = 1 mod 19
        7^4 = 2401 = 126 × 19 + 7 = 7 mod 19
        7^5 = 16807 = 884 × 19 + 11 = 11 mod 19

There is no point in continuing because the sequence is repeating. In other words, the sequence is periodic, and the length of the period is the smallest exponent m such that 7^m = 1 (mod 19).

The Chinese Remainder Theorem

In many situations, it is useful to break a congruence mod n into a system of congruencies mod factors of n. Consider the following example. Suppose we know that a number x satisfies x ≡ 25 (mod 42). This means that we can write x = 25 + 42k for some integer k. rewriting 42 as 7 × 6, we obtain x = 25 + 7 (6k), which implies that x ≡ 25 ≡ 4 (mod 7). Similarly, since x = 25 + 6(7k), we have x ≡ 25 1 (mod 6). Therefore,

x ≡ 25 (mod 42) → x ≡ 4 (mod 7) or x ≡ 1 (mod 6)

The Chinese remainder theorem proves that a system of congruences can be replaced by a single congruence under certain conditions.

The general form of the Chinese Remainder Theorem can be defined as:

m_l, ....., m_k be integers with a gcd (m_i and m_j) whenever i is not equal to j, given integers a_1,.....,a_k there exists exactly one solution x (mod m_1,...m_k) to the simultaneous congruences

x ≡ a^1 (mod m_1), x ≡ a_2 (mod m_2),....., x ≡ a_k (mod m_k)

For example, the theorem guarantees a solution to the simultaneous congruences

x ≡ 1 (mod 11), x ≡ -1 (mod 13), x ≡ 1 (mod 17)

In fact, x ≡ 1871 (mod 11 × 13 × 17) is the answer.

Learn more about the Chinese Remainder Theorem.

Let me know what you think about this article via this contact link.

~~ Thank you for reading