High School Mathematics Extensions/Further Modular Arithmetic

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

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

 

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

   
   

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.

   
   
   

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

 

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

  if and only if  

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

     
   

on the other hand we also get

     
   

Equating the two results, we get

     

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

 
 

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

 
 

for some xn and yn. If rn then r corresponds to

 
 

Now since r and n are different, we must have either xrxn and/or yryn

For example take  , then we can construct the following table showing the  ,   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

 
 

and r corresponds to

 
 

Is it true that

 
 

and that

 
 

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   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

     
   
   

Alternatively, we notice that

 

and

 

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),

     
   
   
   

Now let's solve

 

and

 

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

     
     
     

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

 

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  , and lets multiply 66 and 40 in two ways. Firstly, the standard way

     
   
   

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

     
   
   

For the second example, we notice that there is no need to stop at just two distinct prime factors. We let  , and multiply 900 and 647 (mod 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),

     
   
   

now if we solve the following congruences

 
 
 

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

 

where the last element can be written as (pr-1 - 1)p, and so there are   multiples of p. Therefore we can conclude

 

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

 

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
   
then
   

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

 

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

 

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

 

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

 

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