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₁ (mod m₁)

:

:

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₁₉; 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₂₁; 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₁ (mod m₁)

:

:

x ≡ a_k (mod m_k)

multiply the moduli together, i.e. N=m₁m₂...m_k, then write n₁=N/m₁, ..., n_k=N/m_k.

We then set y_i be the inverse of n_i mod m_i for all i, so y_in_i=1 mod m_i.

Our solution will be

x ≡ a₁y₁n₁+...+a_ky_kn_k (mod N)

To see why this works consider what values x mod m_k takes. The term a_ky_kn_k mod m_k becomes equal to a_k as y_kn_k=1 mod m_k, and all the terms a_jy_jn_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¹⁰=1 in Z₁₁.

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

2⁰=1

2¹=2

2²=1

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

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)²=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)/p_i=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₁₁.

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

2^10/2=2⁵=10

2^10/5=2²=4

Neither is 1, so we can say that 2 is a primitive element in Z₁₁.

Problem set

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

1. Is 4 primitive in Z₁₃?
2. Is 5 primitive in Z₂₃?
3. Find a primitive element of Z₅.
4. Find a primitive element of Z₁₉.

Answers

2. Yes: In Z₂₃, (23-1)=2*11, and 5^22/11=2, 5^22/2=22 and then 5²²=1. No lesser base gives this.

4. 2. Check: (19-1) has distinct prime factors 2 and 3. In Z₁₉, 2^18/2≠1 and 2^18/3≠1 but 2¹⁸=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.

1. φ(p) = p - 1
2. φ(p^k) = p^k-p^k-1
3. φ(mn)=φ(m)φ(n) for gcd(m,n)=1
4. 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_p^k. The non-invertible elements in Z_p^k 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⁴, 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₁ (mod m)

x == a₂ (mod n)

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

Note that a₁ can take on m values (from 0 to m-1), and a₂ can take on n values (from 0 to n-1). Also note that, for each and everyone of the m*n (a₁, a₂) 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₁, a₂) 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₁ is a totient of m and a₂ is a totient of n. Furthermore, you must also show that if a₁ and a₂ 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₁ + k*m

x = a₂ + q*n

Therefore, a₁*X + m*(k + n*Y) = 1,
should this be a₁*X + m*(k*X + n*Y) = 1 ??
so gcd (a₁,m) = 1, and therefore a₁ is a totient of m. Proceed similarly to prove that a₂ 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₁/g and x₂/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₁g and x₂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²¹⁶ in Z₁₄. We need to calculate firstly φ(14)=φ(7)φ(2)=(7-1)(2-1)=6. Then write the exponent as: 216 = 6 × 36 So: 3²¹⁶=(3⁶)³⁶

But Euler's theorem tells us 3⁶=1 in Z₁₄ (i.e., mod 14) since 3^φ(14)=1 in Z₁₄ as above. So we have: 3²¹⁶=1³⁶=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²⁸ in Z₄.

First write 28 in base 2 = (11100)₂ = 2⁴+2³+2² = 16 + 8 + 4

Now 5²⁸ = 5¹⁶⁺⁸⁺⁴ = 5¹⁶ 5⁸ 5⁴ Now rewrite these powers of 2 as repeated exponents:

(((5²)²)²)² × ((5²)²)² × (5²)²

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)

1. 3¹² (mod 13)
2. 2⁴² (mod 43)
3. 6¹⁶⁸ (mod 30)
4. 2²⁵² (mod 19)
5. 2⁶¹ (mod 22)
6. 8¹³ (mod 5)
7. 11¹⁰ (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¹⁸)¹⁴=1.

6. Use fast exponentiation by squaring: the answer is 3