# Discrete Mathematics/Modular arithmetic

## Introduction[edit | edit source]

We have already considered moduli and modular arithmetic back in Number theory, however in this section we will take a more in depth view of modular arithmetic.

For revision, you should review the material in number theory if you choose.

## Simultaneous equations[edit | edit source]

When we speak of simultaneous equations with relation to modular arithmetic, we are talking about simultaneous solutions to sets of equations in the form

*x*≡*a*_{1}(mod m_{1})- :
- :
*x*≡*a*_{k}(mod m_{k})

There are two principal methods we will consider, *successive substitution* and the *Chinese remainder theorem*.

### Successive substitution[edit | edit source]

The method of successive substitution is that where we use the definition of the modulus to rewrite these simultaneous equations, and then successively make substitutions.

It will probably be best to motivate the idea with an example.

**Example:** Solve 3*x* ≡ 10 (mod 19), and *x* ≡ 19 (mod 21) using successive substitution.

First:

- 3
*x*≡ 10 (mod 19)

Find the inverse of 3 in **Z**_{19}; 3^{-1}=-6, then

*x*≡ -60 (mod 19)*x*≡ 16 (mod 19)*x*= 16 + 19*j*∃*j*∈**Z**(*)

Substitute in the second equation

- (16+19
*j*) ≡ 19 (mod 21) - 19
*j*≡ 3 (mod 21)

Find the inverse of 19 in **Z**_{21}; 19^{-1}=10

*j*= 30 (mod 21)

*j*= 9 (mod 21)

Writing in the equivalent form

*j*= 9 + 21*k*∃*k*∈**Z**

Substituting back j in (*)

*x*= 16 + 19(9+21*k*)*x*= 187+399*k*

Writing back in the first form

*x*≡ 187 (mod 399)

which is our solution.

### Chinese remainder theorem[edit | edit source]

The *Chinese remainder theorem* is a method for solving simultaneous linear congruences **when the moduli are coprime**.

Given the equations

*x*≡*a*_{1}(mod m_{1})- :
- :
*x*≡*a*_{k}(mod m_{k})

multiply the moduli together, i.e. N=m_{1}m_{2}...m_{k},
then write n_{1}=N/m_{1}, ..., n_{k}=N/m_{k}.

We then set y_{i} be the inverse of n_{i} mod m_{i} for all i, so y_{i}n_{i}=1 mod m_{i}.

Our solution will be

- x ≡ a
_{1}y_{1}n_{1}+...+a_{k}y_{k}n_{k}(mod N)

To see why this works consider what values x mod m_{k} takes. The term a_{k}y_{k}n_{k} mod m_{k} becomes equal to a_{k} as y_{k}n_{k}=1 mod m_{k}, and all the terms a_{j}y_{j}n_{j} mod m_{k} become equal to zero as when m_{k} is a factor of n_{j}.

The Chinese Remainder Theorem is of immense practical use, as if we wish to solve an equation mod M for some large M, we can instead solve it mod p for every prime factor of M and use CRT to obtain a solution mod M.

## Powers and roots[edit | edit source]

This section deals with looking powers of numbers modulo some modulus. We look at efficient ways of calculating

*a*^{b}(mod*m*)

If we tried to calculate this normally - by calculating *a*^{b} and then taking the modulus - it would take an *exorbitant* amount of time. However some of the theory behind modular arithmetic allows us a few shortcuts.

We will look at some of these and the theory involved with them.

### Fermat's (little) Theorem[edit | edit source]

Fermat's theorem allows us to see where *a*^{b} (mod *m*) is 1. This has an application in disproving primality.

It states

- If p is prime, and gcd(a,p)=1, then, in
**Z**_{p} *a*^{p-1}=1.

So, for example, 13^{10}=1 in **Z**_{11}.

### Primitive elements[edit | edit source]

If in **Z**_{n}, can we write some elements as powers of an element? This is conceivably possible.

Let's look at **Z**_{3}.

- 2
^{0}=1 - 2
^{1}=2 - 2
^{2}=1

The elements {1,2} constitute in fact :**Z**_{3}^{*}.

Generally, we have

- If
*p*prime, then there is an element*g*∈**Z**_{p}^{*}such that every element of**Z**_{p}^{*}is a power of g.

### Orders[edit | edit source]

We can express this idea in a different way, using the concept of the *order*.
We denote the order of *a* ∈ **Z**_{n}^{*} by the smallest integer *k* written O_{n}(a) such that

*a*^{k}=1 in**Z**_{n}.

For example, O_{n}(-1)=2 for all n except 2, since

- (-1)
^{2}=1

except when n = 2, since in that field -1 = 1 and thus has order 1.

**Note** if gcd(*a*,*n*)≠1, that is, *a* ∉ **Z**_{n}^{*}, the order *is not defined*.

#### Properties of orders[edit | edit source]

The orders obey some properties, the first of which was originally proven by Lagrange:

If p prime, gcd(a,p)=1,

- O
_{p}(a) divides p-1 - a is primitive iff O
_{p}(a)=p-1

### Orders and finding primitive elements[edit | edit source]

Given these facts above, we can find primitive elements in **Z**_{p} for *p* > 2 fairly easily.

Using the above facts, we only need to check *a*^{(p-1)/pi}=*x*_{i} in **Z**_{p} for all *i*, where the *p*_{i} are the prime factors of *p*-1. If any of the *x*_{i} are 1, *a* is not a primitive element, if none are, it is.

**Example:** Find a primitive element of **Z**_{11}.

Try 2. *p*-1 = 10 = 2 . 5
Check:

- 2
^{10/2}=2^{5}=10 - 2
^{10/5}=2^{2}=4

Neither is 1, so we can say that 2 is a primitive element in **Z**_{11}.

#### Problem set[edit | edit source]

Given the above, answer the following. (Answers follow to even-numbered questions)

- Is 4 primitive in
**Z**_{13}? - Is 5 primitive in
**Z**_{23}? - Find a primitive element of
**Z**_{5}. - Find a primitive element of
**Z**_{19}.

##### Answers[edit | edit source]

- 2. Yes: In
**Z**_{23}, (23-1)=2*11, and 5^{22/11}=2, 5^{22/2}=22 and then 5^{22}=1. No lesser base gives this. - 4. 2. Check: (19-1) has distinct prime factors 2 and 3. In
**Z**_{19}, 2^{18/2}≠1 and 2^{18/3}≠1 but 2^{18}=1 so 2 is primitive.

### Euler's totient function[edit | edit source]

Euler's totient function is a special function that allows us to generalize Fermat's little theorem above.

It is defined as

- φ(n) = |
**Z**_{n}^{*}|- =|{a∈
**Z**|1 ≤*a*≤*n*and gcd(a,n) = 1}| *that is the number of elements that have inverses in***Z**_{n}

- =|{a∈

#### Some results[edit | edit source]

We have the following results leading on from previous definitions.

- φ(
*p*) =*p*- 1 - φ(
*p*^{k}) =*p*^{k}-*p*^{k-1} - φ(
*mn*)=φ(*m*)φ(*n*) for gcd(*m*,*n*)=1 - For any integer n, the sum of the totient values of each of its divisors equals n.

In other symbols: .

*Proof of 2.*: There are *p*^{k} elements in **Z**_{pk}. The non-invertible elements in **Z**_{pk} are the multiples of *p* and there are *p*^{k-1} of them: *p*, 2*p*, 3*p*, ..., (*p*^{k-1}-1)*p*, *p*^{k}. Removing the non-invertible elements from the invertible ones leaves *p*^{k}-*p*^{k-1} left. ∎

*Corollary to 1, 2 and 3*:
If *n* has distinct prime factors (i.e. not counting powers) *p*_{i} for i=1,...,r we have

For example:

- 16=2
^{4}, so φ(16)=(16)(1-1/2)=16/2=8 - φ(11)=(11)(1-1/11)=(11)(10/11)=10
*(confirm from before 11 prime so φ(11)=11-1=10)*.

*Proof of 3.*: We can prove this equality using a special case of the Chinese Remainder Theorem, where the CRT is now just a system of 2 congruences, namely:

- x == a
_{1}(mod m) - x == a
_{2}(mod n)

(remember that the CRT is applicable here because m and n are assumed coprime in the equality).

Note that a_{1} can take on m values (from 0 to m-1), and a_{2} can take on n values (from 0 to n-1). Also note that, for each and everyone of the m*n (a_{1}, a_{2}) tuples, there is a unique solution x that is strictly smaller than m*n. Moreover, for each x strictly smaller than m*n, there is a unique tuple (a_{1}, a_{2}) verifying the congruence system (these two assertions are a component of the Chinese Remainder Theorem: a solution to the congruence system is unique modulo m*n).

With this bijective uniqueness property in mind, the proof is simple. Go through each x, from 0 to m*n-1, and show that if x is a totient of m*n (i.e., gcd (x,m*n) = 1), then a_{1} is a totient of m and a_{2} is a totient of n. Furthermore, you must also show that if a_{1} and a_{2} are totients of m and n respectively, then it follows that x must be a totient of m*n.

If gcd (x,m*n) = 1, then according to Bezout's identity, there exist X and Y integers such that x*X + m*n*Y = 1. Furthermore, we have:

- x = a
_{1}+ k*m - x = a
_{2}+ q*n

Therefore, a_{1}*X + m*(k + n*Y) = 1, ** should this be a _{1}*X + m*(k*X + n*Y) = 1 ?? **
so gcd (a

_{1},m) = 1, and therefore a

_{1}is a totient of m. Proceed similarly to prove that a

_{2}is a totient of n.

Proving the other direction is very similar in that it requires some simple replacement algebra.

So what have we shown? In the above we have shown that for every totient x of m*n, there is a unique tuple of totients of m on the one hand and n on the other hand. Furthermore, that for each tuple of totients of m on the one hand and n on the other hand, there is a unique totient of m*n. Therefore, phi(m*n) = phi(m)*phi(n).

*Proof of 4.*: Let Q(g) be the set of all integers between 1 and n inclusive, such that
gcd(x,n) = g. Q(g) is nonempty if and only if g divides n. If g doesn't divide n, then good luck
finding an x such that g is the greatest common DIVISOR of x and n. Secondly, if x belongs to
Q(g) for a given g, then it can't belong to another Q(...), since, if n is fixed, then
gcd(x,n) is unique, by definition of the GREATEST common divisor. Thirdly, for all x between
1 and n inclusive, there exists a g such that gcd (x,n) = g (in the "worst" case, it's 1).
Put together, these three properties imply that the union of all the Q(g) sets (for each g a
divisor of n), which are pairwise mutually exclusive, is the set {1,2,3,...,n}. And therefore, the sum of the cardinalities of each Q(g) equals n.

Now we show that |Q(g)| = φ(n/g).

One direction: Let x be an arbitrary member of Q(g) for some g. Therefore, we have that
gcd (x,n) = g => gcd (x/g, n/g) = 1 => x/g belongs to the set of numbers coprime to n/g (whose cardinality of course is φ(n/g)). For diff\
erent x's, the two values x_{1}/g and x_{2}/g are distinct. So for each x in Q(g), there is a correspondingly unique x/g in
the set of numbers coprime to n/g.

Other direction: Let x be an arbitrary member of the set of numbers coprime to n/g. This implies
gcd (x,n/g) = 1 => gcd (xg,n) = g => xg belongs to Q(g). For different x's, the two values
x_{1}g and x_{2}g are distinct. So for each x in the set of numbers coprime to
n/g, there is a correspondingly unique xg in Q(g).

Therefore, |Q(g)| = φ(n/g).

### Euler's theorem[edit | edit source]

We can now generalize Fermat's theorem to extend past just **Z**_{n}.

Euler's theorem says:

- If a ∈
**Z**_{n}^{*}, in**Z**_{n}^{*},- a
^{φ(n)}=1

- a
- equivalently if gcd(
*a*,*n*)=1,- a
^{φ(n)}≡1 (mod*n*)

- a

**Example:** Find 3^{216} in **Z**_{14}.
We need to calculate firstly φ(14)=φ(7)φ(2)=(7-1)(2-1)=6.
Then write the exponent as: 216 = 6 × 36
So: 3^{216}=(3^{6})^{36}

But Euler's theorem tells us 3^{6}=1 in **Z**_{14} (i.e., mod 14) since 3^{φ(14)}=1 in **Z**_{14} as above.
So we have: 3^{216}=1^{36}=1.

### Calculating large powers efficiently[edit | edit source]

When Euler's or Fermat's theorem fails us in the calculation of a high power, there is a way to decompose an exponent down so calculation is still easy.

Let us work through an example as motivation.

**Example.** 5^{28} in **Z**_{4}.

First write 28 in base 2 = (11100)_{2} = 2^{4}+2^{3}+2^{2} = 16 + 8 + 4

Now 5^{28} = 5^{16+8+4} = 5^{16} 5^{8} 5^{4}
Now rewrite these powers of 2 as repeated exponents:

- (((5
^{2})^{2})^{2})^{2}× ((5^{2})^{2})^{2}× (5^{2})^{2}

When you calculate each exponent, reduce mod 4 each time.

#### Problem set[edit | edit source]

Given the above, calculate the following powers. (Answers follow to even-numbered questions)

- 3
^{12}(mod 13) - 2
^{42}(mod 43) - 6
^{168}(mod 30) - 2
^{252}(mod 19) - 2
^{61}(mod 22) - 8
^{13}(mod 5) - 11
^{10}(mod 11) (*Tricky!*)

##### Answers[edit | edit source]

- 2. Since gcd(2,43)=1 and the exponent is one less than the modulus, use Fermat's theorem - the answer is 1
- 4. Observe that φ(19)=18 and 18|252. 252/18=14. Decompose the exponent then as 2
^{18×14}=(2^{18})^{14}=1. - 6. Use fast exponentiation by squaring: the answer is 3