High School Mathematics Extensions/Further Modular Arithmetic

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

HSME
Content
Further Modular Arithmetic
Multiplicative Group and Discrete Log
Problems & Projects
Problem Set
Project
Solutions
Exercises Solutions
Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Introduction

Mathematics is the queen of the sciences and number theory is the queen of mathematics. -- Carl Friedrich Gauss 1777 - 1855

In the Primes and Modular Arithmetic section, we discussed the elementary properties of a prime and its connection to modular arithmetic. For the most part our attention has been restricted to arithmetic mod p, where p is prime.

In this chapter, we start by discussing some more elementary results in arithmetic modulo a prime p, and then moving on to discuss those results modulo m where m is composite. In particular, we will take a closer look at the Chinese Remainder Theorem (CRT), and how it allows us to break arithmetic modulo m into components. From that point of view, the CRT is an extremely powerful tool that can help us unlock the many secrets of modulo arithmetic (with relative ease).

Lastly, we will introduce the idea of an abelian group through multiplication in modular arithmetic and discuss the discrete log problem which underpins one of the most important cryptographic systems known today.

Assumed knowledge In this chapter we assume the reader can find inverses and be able to solve a system of congruences (Chinese Remainder Theorem) (see: Primes and Modular Arithmetic).

Wilson's Theorem

Wilson's theorem is a simple result that leads to a number of interesting observations in elementary number theory. It states that, if p is prime then

$1\cdot 2\cdot 3\cdots (p-1)\equiv p-1{\pmod {p}}$

We know the inverse of p - 1 is p - 1, so each other number can be paired up by its inverse and eliminated. For example, let p = 7, we consider

1 × 2 × .. × 6 ≡ (2 × 4) × (3 × 5) × 1 × 6 = 6

What we have done is that we paired up numbers that are inverses of each other, then we are left with numbers whose inverse is itself. In this case, they are 1 and 6.

But there is a technical difficulty. For a general prime number, p, how do we know that 1 and p - 1 are the only numbers in mod p which when squared give 1? For m not a prime, there are more than 2 solutions to x² ≡ 1 (mod m), for example, let m = 15, then x = 1, 14, 4, 11 are solutions to x² ≡ 1 (mod m).

However, we can show that there can only be (at most) two solutions to x² ≡ 1 (mod p) when p is prime. We do that by a simple proof by contradiction argument. You may want to skip the following proof and come up with your own justification of why Wilson's theorem is true.

Let p be a prime, and x² ≡ 1 (mod p). We aim to prove that there can only be 2 solutions, namely x = 1, -1

$x^{2}-1\!$	$\equiv 0\!$
$(x-1)(x+1)\!$	$\equiv 0\!$

it obvious from the above that x = 1, -1 (≡ p - 1) are solutions. Suppose there is another solution, x = d, and d not equal to 1 or -1. Since p is prime, we know d - 1 must have an inverse. We substitute x with d and multiply both sides by the inverse, i.e.

$(d-1)(d+1)\!$	$=0\!$
$d+1\!$	$=0\!$
$d\!$	$=-1\!$

but we our initial assumption was that d ≠ -1. This is a contradiction. Therefore there can only be 2 solutions to x² ≡ 1 (mod p).

Fermat's little Theorem

There is a remarkable little theorem named after Fermat, the prince of amateur mathematicians. It states that if p is prime and given a ≠ 0 then

$a^{p-1}\equiv 1{\pmod {p}}\!$

This theorem hinges on the fact that p is prime. Recall that if p is prime then a ≠ 0 has an inverse. So for any b and c we must have

$ab\equiv ac{\pmod {p}}\!$ if and only if $b\equiv c{\pmod {p}}\!$

A simple consequence of the above is that the following numbers must all be different mod p

a, 2a , 3a, 4a, ..., (p-1)a

and there are p - 1 of these numbers! Therefore the above list is just the numbers 1, 2, ... p - 1 in a different order. Let's see an example, take p = 5, and a = 2:

1, 2, 3, 4

multiply each of the above by 2 in mod 5, we get

2, 4, 1, 3

They are just the original numbers in a different order.

So for any p and using Wilson's Theorem (recall: 1 × 2 × ... × (p-1) ≡ -1), we get

$a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$1\cdot 2\cdots (p-1)$
	$\equiv \!$	$-1\!$

on the other hand we also get

$a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$a^{p-1}(1\cdot 2\cdots (p-1))$
	$\equiv \!$	$-a^{p-1}\!$

Equating the two results, we get

$-a^{p-1}\!$

$\equiv \!$

$-1\!$

which is essentially Fermat's little theorem.

Modular Arithmetic with a general m

*Chinese Remainder Theorem revisited*

This section is rather theoretical, and is aimed at justifying the arithmetic we will cover in the next section. Therefore it is not necessary to fully understand the material here, and the reader may safely choose to skip the material below.

Recall the Chinese Remainder Theorem (CRT) we covered in the Modular Arithmetic section. In states that the following congruences

$x\equiv b{\pmod {n_{1}}}\!$

$x\equiv c{\pmod {n_{2}}}\!$

have a solution if and only if gcd(n₁,n₂) divides (b - c).

This deceptively simple theorem holds the key to arithmetic modulo m (not prime)! We shall consider the case where m has only two prime factors, and then the general case shall follow.

Suppose m = pⁱq^j, where p and q are distinct primes, then every natural number below m (0, 1, 2, ..., m - 1) corresponds uniquely to a system of congruence mod pⁱ and mod q^j. This is due to the fact that gcd(pⁱ,q^j) = 1, so it divides all numbers.

Consider a number n, it corresponds to

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

for some x_n and y_n. If r ≠ n then r corresponds to

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

Now since r and n are different, we must have either x_r ≠ x_n and/or y_r ≠ y_n

For example take $m=12=2^{2}\times 3$, then we can construct the following table showing the $x_{n}$, $y_{n}$ for each n (0, 1, 2 ... 11)

n	n (mod 22)	n (mod 3)
0	0	0
1	1	1
2	2	2
3	3	0
4	0	1
5	1	2
6	2	0
7	3	1
8	0	2
9	1	0
10	2	1
11	3	2

Note that as predicted each number corresponds uniquely to two different systems of congruences mod 2² and mod 3.

Exercises

1. Consider m = 45 = 3² × 5. Complete the table below and verify that any two numbers must differ in at least one place in the second and third column

n	n (mod 32)	n (mod 5)
0	0	0
1	1	1
2	2	2
...
44	?	?

2. Suppose m = pⁱq^j, n corresponds to

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

and r corresponds to

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

Is it true that

$n+r\equiv x_{n}+x_{r}{\pmod {p^{i}}}\!$

$n+r\equiv y_{n}+y_{r}{\pmod {q^{j}}}\!$

and that

$nr\equiv x_{n}x_{r}{\pmod {p^{i}}}\!$

$nr\equiv y_{n}y_{r}{\pmod {q^{j}}}\!$

Arithmetic with CRT

Exercise 2 above gave the biggest indication yet as to how the CRT can help with arithmetic modulo m. It is not essential for the reader to fully understand the above at this stage. We will proceed to describe how CRT can help with arithmetic modulo m. In simple terms, the CRT helps to break a modulo-m calculation into smaller calculations modulo prime factors of m.

As always, let's consider a simple example first. Let $m=63=3^{2}\ \times \ 7$ and we see that m has two distinct prime factors. We should demonstrate multiplication of 51 and 13 modulo 63 in two ways. Firstly, the standard way

$51\times 13\!$	$=\!$	$663\!$
	$=\!$	$10\times 63+33\!$
	$\equiv \!$	$33{\pmod {63}}\!$

Alternatively, we notice that

$51\equiv 6{\pmod {9}}\!$

and

$51\equiv 2{\pmod {7}}\!$

We can represent the two expressions above as a two-tuple (6,2). We abuse the notation a little by writing 51 = (6,2). Similarly, we write 13 = (4,6). When we do multiplication with two-tuples, we multiply component-wise, i.e. (a,b) × (c,d) = (ac,bd),

$51\times 13\!$	$=\!$	$(6,2)\times (4,6)\!$
	$=\!$	$(24,12)\!$
	$=\!$	$(2\times 9+6,7+5)\!$
	$\equiv \!$	$(6,5)\!$

Now let's solve

$x\equiv 6{\pmod {9}}\!$

and

$x\equiv 5{\pmod {7}}\!$

we write x = 6 + 9a, which is the first congruence equation, and then

$6+9a\!$	$\equiv \!$	$5{\pmod {7}}\!$
$2a\!$	$\equiv \!$	$6\!$
$a\!$	$\equiv \!$	$3\!$

therefore we have a = 3 + 7b, substitute back to get

$x=6+9(3+7b)=33+63b\equiv 33{\pmod {63}}\!$

which is the same answer we got from multiplying 51 and 13 (mod 63) the standard way!

Let's summarise what we did. By representing the two numbers (51 and 13) as two two-tuples and multiplying component-wise, we ended up with another two-tuple. And this two-tuple corresponds to the product of the two numbers (mod m) via the Chinese Remainder Theorem.

We will do two more examples. Let $m=88=2^{3}\times 11$, and lets multiply 66 and 40 in two ways. Firstly, the standard way

$66\times 40\!$	$=\!$	$2640\!$
	$=\!$	$30\times 88\!$
	$\equiv \!$	$0{\pmod {88}}\!$

and now the second way, 40 = (0,7) and 66 = (4,0) and

$66\times 40\!$	$=\!$	$(0,7)\times (4,0)\!$
	$=\!$	$(0,0)\!$
	$\equiv \!$	$0{\pmod {88}}\!$

For the second example, we notice that there is no need to stop at just two distinct prime factors. We let $m=975=3\times 5^{2}\times 13$, and multiply 900 and 647 (mod 975),

$900\times 647\!$	$=\!$	$582300\!$
	$\equiv \!$	$225{\pmod {975}}\!$

For the other way, we note that 900 ≡ 0 (mod 3) ≡ 0 (mod 25) ≡ 3 (mod 13), and for 647 ≡ 2 (mod 3) ≡ 22 (mod 25) ≡ 10 (mod 13),

$900\times 647\!$	$=\!$	$(0,0,3)\times (2,22,10)\!$
	$\equiv \!$	$(0,0,30)\!$
	$\equiv \!$	$(0,0,4)\!$

now if we solve the following congruences

$x\equiv 0{\pmod {3}}\!$

$x\equiv 0{\pmod {25}}\!$

$x\equiv 4{\pmod {13}}\!$

then we will get x ≡ 225!

Why? If anything, breaking modular arithmetic in m into smaller components seems to be quite a bit of work. Take the example of multiplications, firstly, we need to express each number as a n-tuple (n is the number of distinct prime factors of m), multiply component-wise and then solve the resultant n congruences. Surely, it must be more complicated than just multiplying the two numbers and then reduce the result modulo m. So why bother studying it at all?

By breaking a number m into prime factors, we have gained insight into how the arithmetic really works. More importantly, many problems in modular m can be difficult to solve, but when broken into components it suddenly becomes quite easy, e.g. Wilson's Theorem for a general m (discussed below).

Exercises

1. Show that addition can also be done component-wise.

2. Multiply component-wise 32 and 84 (mod 134).

...

Euler totient

To discuss the more general form of Wilson's Theorem and Fermat's Little Theorem in mod m (not prime), it's nice to know a simple result from the famous mathematician Euler. More specifically, we want to discuss a function, called the Euler totient function (or Euler Phi), denoted φ.

The φ functions does a very simple thing. For any natural number m, φ(m) gives the number of n < m, such that gcd(n,m) = 1. In other words, it calculates how many numbers in mod m have an inverse. We will discuss the value of φ(m) for simple cases first and then derive the formula for a general m from the basic results.

For example, let m = 5, then φ(m) = 4. As 5 is prime, all non-zero natural numbers below 5 (1,2,3 and 4) are coprimes to it. So there are 4 numbers in mod 5 that have inverses. In fact, if m is prime then φ(m) = m - 1.

We can generalise the above to m = p^r where p is prime. In this case, we try to employ a counting argument to calculate φ(m). Note that there are p^r natural numbers below m (0, 1, 2 ... p^r - 1), and so φ(m) = p^r - (number of n < m such that gcd(n,m) ≠ 1). We did that because it is easier to count the number of n 's without an inverse mod m.

An element, n, in mod m does not have an inverse if and only if it shares a common factor with m. But all factors of m (not equal to 1) are a multiple of p. So how many multiples of p are there in mod m? We can list them, they are

$0,p,2p,\cdots ,p^{r}-p\!$

where the last element can be written as (p^r-1 - 1)p, and so there are $p^{r-1}\!$ multiples of p. Therefore we can conclude

$\phi (p^{r})=p^{r}-p^{r-1}\!$

We now have all the machinery necessary to derive the formula of φ(m) for any m.

By the Fundamental Theorem of Arithmetic, any natural number m can be uniquely expressed as the product of primes, that is

$m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$

where p_i for i = 1, 2 ... r are distinct primes and k_i are positive integers. For example 1225275 = 3×5²×17×31². From here, the reader should try to derive the following result (the CRT may help).

Euler totient function φ

Suppose m can be uniquely expressed as below
  $m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$
then
  $\phi (m)=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})(p_{2}^{k_{2}}-p_{2}^{k_{2}-1})\cdots (p_{r}^{k_{r}}-p_{r}^{k_{r}-1})\!$

With the Euler totient function we can derive a more general case of Fermat's Little Theorem, that is:

$a^{\phi (m)}\equiv 1{\pmod {m}}\$

Wilson's Theorem

Wilson's Theorem for a general m states that the product of all the invertible element in mod m

equals -1 if m has only one prime factor, or m = 2p^k for some prime p

equals 1 for all other cases

An invertible element of mod m is a natural number n < m such that gcd(n, m) = 1. A self-invertible element is an element whose inverse is itself.

In the proof of Wilson's Theorem for a prime p, the numbers 1 to p - 1 all have inverses. This is not true for a general m. In fact it is certain that (m - 1)! ≡ 0 (mod m), for this reason we instead consider the product of all invertible elements in mod m.

For the case where m = p is prime we also appealed to the fact 1 and p - 1 are the only elements when squared gives 1. In fact for m = p^k, 1 and m - 1 (≡ -1)are the only self-invertible elements (see exercise). But for a general m, this is not true. Let's take for example m = 21. In arithmetic modulo 21 each of the following numbers has itself as an inverse

1, 20, 8, 13

so how can we say the product of all invertible elements equal to 1?

We use the CRT described above. Let us consider the case where m = 2p^k. By the CRT, each element in mod m can be represented as a two tuple (a,b) where a can take the value 0 or 1 while b can take the value 0, 1, ..., or p^k - 1. Each two tuple corresponds uniquely to a pair of congruence equations and multiplication can be performed component-wise.

Using the above information, we can easily list all the self-invertible elements, because (a,b)² ≡ 1 means (a²,b²) = (1,1), so a is an invertible element in mod 2 and b is an invertible element in mod p^k, so a ≡ 1 or -1, b ≡ 1 or -1. But in mod 2 1 ≡ -1, so a = 1. Therefore, there are two elements that are self invertible in mod m = 2p^k, they are (1,1) = 1, and (1, -1) = m - 1 . So in this case, the result is the same as when m has only a single prime factor.

For the case where m has more than one prime factors and m≠ 2p^k. Let say m has n prime factors then m can be represented as a n-tuple. Let say m has 3 distinct prime factors, then all the self-invertible elements of m are

1. (1,1,1)
2. (1,1,-1)
3. (1,-1,1)
4. (1,-1,-1)
5. (-1,1,1)
6. (-1,1,-1)
7. (-1,-1,1)
8. (-1,-1,-1)

their product is (1,1,1) which corresponds to 1 in mod m.

Exercise

1. Let p be a prime. Show that in arithmetic modulo p^k, 1 and p^k - 1 are the only self-invertible elements.

...more to come

Fermat's Little Theorem

As mentioned in the previous section, not every element is invertible (i.e. has an inverse) mod m. A generalised version of Fermat's Last Theorem uses Euler's Totient function, it states

$a^{\phi (m)}\equiv 1{\pmod {m}}\!$

for all a ≠ 0 satisfying gcd(a,m) = 1. This is easy to see from the generalised version of Wilson's Theorem. We use a similar technique from the prove of Fermat's Little Theorem. We have

$(ab_{1})(ab_{2})\cdots (ab_{\phi (m)})\equiv b_{1}b_{2}\cdots b_{\phi (m)}{\pmod {m}}$

where the b_i's are all the invertible elements mod m. By Wilson's theorem the product of all the invertible elements equals to, say, d (= 1 or -1). So we get

$a^{\phi (m)}d\equiv d{\pmod {m}}\!$

which is essentially the statement of Fermat's Little Theorem.

Although the FLT is very neat, it is imprecise in some sense. For example take m = 15 = 3 × 5, we know that if a has an inverse mod 15 then a^φ(15) = a⁸ ≡ 1 (mod 15). But 8 is too large, all we need is 4, by that we mean, a⁴ ≡ 1 (mod 15) for all a with an inverse (the reader can check).

The Carmichael function λ(m) is the smallest number such that a^λ(m) ≡ 1 (mod m) for invertible a. A question in the Problem Set deals with this function.

Exercises

...more to come

Two-torsion Factorisation

It it quite clear that factorising a large number can be extremely difficult. For example, given that 76372591715434667 is the product of two primes, can the reader factorise it? Without the help of a good computer algebra software, the task is close to being impossible. As of today, there is no known efficient all purpose algorithm for factorising a number into prime factors.

However, under certain special circumstances, factorising can be easy. We shall consider the two-torsion factorisation method. A two-torsion element in modular m arithmetic is a number a such that a² ≡ 1 (mod m).

Let's consider an example in arithmetic modulo 21. Note that using the CRT we can represent any number in mod 21 as a two-tuple. We note that the two-torsion elements are 1 = (1,1), 13 = (1,-1), 8 = (-1,1) and 20 = (-1,-1). Of interest are the numbers 13 and 8, because 1 and 20 (≡ - 1) are obviously two-torsion, we call these numbers trivially two-torsion.

Now, 13 + 1 = (1,-1) + (1,1) = (2,0). Therefore 13 + 1 = 14 is an element sharing a common factor with 21, as the second component in the two-tuple representation of 14 is zero. Therefore GCD(14,21) = 7 is a factor of 21.

The above example is very silly because anyone can factorise 21. But what about 24131? Factorising it is not so easy. But, if we are given that 12271 is a non-trivial (i.e. ≠ 1 or -1) two-torsion element, then we can conclude that both gcd(12271 + 1,24131) and gcd(12271 - 1,24131) are factors of 24131. Indeed gcd(12272,24131) = 59 and gcd(12270,24131) = 409 are both factors of 24131.

More generally, let m be a composite, and t be a non-trivial two-torsion element mod m i.e. t ≠ 1, -1. Then

gcd(t + 1,m) divides m, and

gdc(t - 1,m) divides m

this can be explained using the CRT.

We shall explain the case where m = pq and p and q are primes. Given t is a non-trivial two-torsion element, then t has representaion (1,-1) or (-1,1). Suppose t = (-1,1) then t + 1 = (-1,1) + (1,1) = (0,2), therefore t + 1 must be a multiple of p therefore gcd(t,m) = p. In the other case where t - 1 = (-1,1) - (1,1) = (-2,0) and so gcd(t - 1,m) = q.

So if we are given a non-trivial two-torsion element then we have effectively found one (and possibly more) prime factors, which goes a long way in factorising the number. In most modern public key cryptography applications, to break the system we need only to factorise a number with two prime factors. In that regard two-torsion factorisation method is frightening effectively.

Of course, finding a non-trivial two-torsion element is not an easy task either. So internet banking is still safe for the moment. By the way 76372591715434667 = 224364191 × 340395637.

Exercises

1. Given that 18815 is a two-torsion element mod 26176. Factorise 26176.

...more to come'

Next Section

Next Section: Multiplicative Group

Problem Set Problem Set