# Discrete Mathematics/Modular arithmetic
## Introduction

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

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

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 3x ≡ 10 (mod 19), and x ≡ 19 (mod 21) using successive substitution.
First:
    3x ≡ 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 + 19j ∃ j∈Z (*)
Substitute in the second equation
    (16+19j) ≡ 19 (mod 21)
    19j ≡ 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 + 21k ∃ k∈Z
Substituting back j in (*)
    x = 16 + 19(9+21k)
    x = 187+399k
Writing back in the first form
    x ≡ 187 (mod 399)
which is our solution.

### Chinese remainder theorem

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 $j\neq k$ 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

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

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

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

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

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

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

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

    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

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$

#### Some results

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: $\sum _{d\ divisor\ of\ n}\phi (d)=n$.
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, 2p, 3p, ..., (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
    $\phi (n)=n\prod _{i=1}^{r}(1-{\frac {1}{p_{i}}})$
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

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
    equivalently if gcd(a,n)=1,
       a$^{φ(n)}$≡1 (mod n)
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

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

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

    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