High School Mathematics Extensions/Further Modular Arithmetic

From Wikibooks, open books for an open world
< High School Mathematics Extensions
Jump to: navigation, search
HSME
Content
100 percents.svg Further Modular Arithmetic
100 percents.svg Multiplicative Group and Discrete Log
Problems & Projects
100 percents.svg Problem Set
100 percents.svg Project
Solutions
100 percents.svg Exercises Solutions
50%.svg Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Introduction[edit]

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[edit]

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 x2 ≡ 1 (mod m), for example, let m = 15, then x = 1, 14, 4, 11 are solutions to x2 ≡ 1 (mod m).

However, we can show that there can only be (at most) two solutions to x2 ≡ 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 x2 ≡ 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 x2 ≡ 1 (mod p).

Fermat's little Theorem[edit]

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[edit]

*Chinese Remainder Theorem revisited*[edit]

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(n1,n2) 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 = piqj, 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 pi and mod qj. This is due to the fact that gcd(pi,qj) = 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 xn and yn. If rn 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 xrxn and/or yryn

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 22 and mod 3.

Exercises

1. Consider m = 45 = 32 × 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 = piqj, 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_nx_r \pmod{p^i} \!
nr \equiv y_ny_r\pmod{q^j} \!

Arithmetic with CRT[edit]

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[edit]

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

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

...

Euler totient[edit]

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 = pr where p is prime. In this case, we try to employ a counting argument to calculate φ(m). Note that there are pr natural numbers below m (0, 1, 2 ... pr - 1), and so φ(m) = pr - (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 (pr-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 pi for i = 1, 2 ... r are distinct primes and ki are positive integers. For example 1225275 = 3×52×17×312. 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[edit]

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 = 2pk 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 = pk, 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 = 2pk. 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 pk - 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)2 ≡ 1 means (a2,b2) = (1,1), so a is an invertible element in mod 2 and b is an invertible element in mod pk, 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 = 2pk, 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≠ 2pk. 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[edit]

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

...more to come

Fermat's Little Theorem[edit]

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_1b_2\cdots b_{\phi(m)} \pmod m

where the bi'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) = a8 ≡ 1 (mod 15). But 8 is too large, all we need is 4, by that we mean, a4 ≡ 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[edit]

...more to come

Two-torsion Factorisation[edit]

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 a2 ≡ 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[edit]

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

...more to come'

Next Section[edit]

Next Section: Multiplicative Group

Problem Set Problem Set