Some Number Theory

Most public key systems rely on number-theoretic results. Before we can discuss the implementation of one, we need to quickly go over the necessary background. We have already used a tiny amount of number theory (in our discussion of computing mod p and of the greatest common divisor). Of course, this must be done briefly, and we will only touch on a small part of a large and ancient field-- the interested reader would do well to consult a text on number theory for more information.

The greatest common divisor and the Euclidean algorithm

We have already met the greatest common divisor, or gcd, which is the largest integer which divides both of a pair of numbers. Two numbers are said to be relatively prime if their greatest common divisor is 1. As we have already seen, finding two relatively prime numbers has important applications in many cryptosystems.

How can we determine the gcd of two numbers? If the numbers are not too large, just looking at their factors does the trick. For example,

gcd(138, 126) = 6    since     138 = 2 ^. 3 ^. 23   and   126 = 2 ^. 3^{2 .} 7

However, there must be a more efficient way, since maple can calculate the gcd of two 60-digit numbers in well under a second, while taking a long time (about 30 minutes on a 200 MHZ pentium computer) to factor either one of them.

One such algorithm is the Euclidean algorithm, which has been around for thousands of years. It works by computing successive differences-- to compute gcd(a, b), where a > b, we first compute r₁ = a - k₁b, where k₁b is the largest multiple of b that is less than a. Then we repeat this, finding r₂ = b - k₂r₁, r₃ = r₁ - k₃r₂, and so on until the remainder is zero. The last nonzero remainder is the gcd. For example, to calculate gcd(138, 126),

a		=	138
	b	=	126
a	- b	=	12
-10a	+11b	=	6
21a	-23b	=	0

This not only gives gcd(138, 126), but expresses it as a difference of multiples of the two numbers: 6 = 11 ^. 126 - 10 ^. 138. We can write this procedure more formally as a theorem.

Theorem 3.10.1   (The Euclidean Algorithm)  Let a and b be two positive integers, with b < a. Then we can construct two decreasing sequences of positive integers r_i and k_i as follows:

k1b	+	r1	=	a		0 < r1 < b
k2r1	+	r2	=	b		0 < r2 < r1
k3r2	+	r3	=	r1		0 < r3 < r2
k4r3	+	r4	=	r2		0 < r4 < r3
			$$\vdots$$
knrn - 1	+	rn	=	rn - 2		0 < rn < rn - 1
kn + 1rn			=	rn - 1

and r_n is the greatest common divisor of a and b.

We have already seen that the Euclidean algorithm also gives us the following:

Corollary 3.10.2   Let a and b be two positive integers. Then there are integers x and yso that ax + by = gcd(a, b).

Before proving Thm. 10.1, we will need a lemma.

Lemma 3.10.3   Let a be a positive integer, and b be a nonnegative integer. If

b = aq + r,                with q and r positive integers

then gcd(a, b) = gcd(a, r).

Proof.  Let d = gcd(a, b). Then since d is a divisor of a and a divisor of b, it is also a divisor of b - aq. Since r = b - aq, we have d a divisor of r. So it must divide gcd(a, r).

Now, in order to prove equality, we want to show that also gcd(a, r) is a divisor of d. Certainly gcd(a, r) divides b, since b = r + aq. It also divides a, and so we have gcd(a, r) as a divisor of gcd(a, b).

Thus, gcd(a, r) = gcd(a, b). $\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

Now we are ready to prove Thm. 10.1:

Proof.  Notice that the sequence b > r₁ > r₂ > r₃ >... is a strictly decreasing sequence of positive integers, so it must eventually terminate with some r_n > 0. The last equation, k_{n + 1}r_n = r_{n - 1} says that r_nis a divisor of r_{n - 1}, so certainly r_n = gcd(r_n, r_{n - 1}). Applying the lemma to the equation above it gives gcd(r_n, r_{n - 1}) = gcd(r_{n - 1}, r_{n - 2}). We can construct the following chain in this way:

r_n = gcd(r_n, r_{n - 1}) = gcd(r_{n - 1}, r_{n - 2}) =...= gcd(r₁, b) = gcd(a, b)

$\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

Recall that if r is such that ar = 1, then r is called the multiplicative inverse of a. We have already dealt with such objects extensively. We now state a theorem which tells us exactly when such inverses exist. Note that this is really just Prop. 7.1 slightly reworded.

Theorem 3.10.4   Let a and n be integers, with n$\ge$2. Then a has a multiplicative inverse modulo n if and only if gcd(a, n) = 1.

Proof.  First, suppose that a has an inverse modulo n. Then there is a k so that

ak $$\equiv$$ 1 mod n.

In particular, n is a divisor of ak - 1, so there must be some integer t so that ak - 1 = nt. Rewriting this as

ak - nt = 1,

we see that gcd(a, n) = 1.

Now suppose that gcd(a, n) = 1. Then by Cor. 10.2, there are integers r and s with ar + ns = 1. This means ar - 1 is divisible by n, so

ar $$\equiv$$ 1 mod n.

But this says that r is the inverse of a mod n. $\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

Notation.  We haven't yet used this notation, but it is common to denote the set of integers modulo n as $\mbox{${ \mathbb{ Z}}$}$_n. That is,

$$\mbox{${\mathbb{ Z} }$}$$_n = $$\left\{\vphantom{{0, 1, 2, \ldots, n-1}}\right.$$0, 1, 2,..., n-1$$\left.\vphantom{{0, 1, 2, \ldots, n-1}}\right\}$$

As we have already know, this set is closed under addition and multiplication, and the usual associative, distributive, and commutativity laws hold. In fact, this set forms a ring.

Notation. We will use $\mbox{${ \mathbb{ Z}}$}$_n^* to denote the elements of $\mbox{${ \mathbb{ Z}}$}$_n which that have multiplicative inverses. In light of the last theorem, we have

$$\mbox{${\mathbb{ Z} }$}$$_n^* = $$\left\{\vphantom{{a \in \mbox{${\mathbb{ Z} }$}_n \,\,\vrule{}\,\,\gcd(a,n)=1 }}\right.$$a $$\in$$ $$\mbox{${\mathbb{ Z} }$}$$_n    gcd(a, n)=1$$\left.\vphantom{{a \in \mbox{${\mathbb{ Z} }$}_n \,\,\vrule{}\,\,\gcd(a,n)=1 }}\right\}$$

The Chinese Remainder Theorem

In this section, we state a very old theorem about simultaneous solutions to congruences. This theorem may have been known to the eight-century Buddhist monk I-Hsing, and certainly appears in Ch'in Chiu-shao's Mathematical Treatise in Nine Sections, written in 1247. It is sometimes (rarely) referred to as the ``Formosa Theorem''.

Theorem 3.10.5   Let m$\ge$2 and n$\ge$2 be integers with gcd(m, n) = 1. Then for any integers a and b, the system of equations

x $$\equiv$$ a	mod m
x $$\equiv$$ b	mod n

has a solution. Furthermore, there is only one solution x between 0 and mn - 1.

Proof.  Since m and n are relatively prime, there are integers k and t so that mk + nt = 1. Then

c = bkm + ant

is the desired solution. To verify this, we need only check:

c $$\equiv$$ ant $$\equiv$$ a(1 - mk) $$\equiv$$ a  mod m

and

c $$\equiv$$ bkm $$\equiv$$ b(1 - nt) $$\equiv$$ b  mod n.

To check uniqueness, suppose there are two solutions c and d. Since c $\equiv$ a mod m and d $\equiv$ a mod m. We have c - d $\equiv$ 0 mod m and c - d $\equiv$ 0 mod n. Since both m and n divide c - d, and m and nare relatively prime, we have that mn divides c - d. Thus c - d $\equiv$ 0 mod mn, that is, c $\equiv$ d mod mn.

Powers modulo n

Notation.  In this and future sections, we shall use the notation $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a}}\right]\kern-.32em\right]}_{b}$}$ to denote a mod b.

First, let's take a look at a few examples of what happens when we reduce the sequence a, a², a³, a⁴,... modulo n. Consider $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{3^k}}\right]\kern-.32em\right]}_{20}$}$:

3, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{3^2}}\right]\kern-.32em\right]}_{20}$}$$ = 9, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{3^3}}\right]\kern-.32em\right]}_{20}$}$$ = 7, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{3^4}}\right]\kern-.32em\right]}_{20}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{21}}\right]\kern-.32em\right]}_{20}$}$$ = 1, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{3^5}}\right]\kern-.32em\right]}_{20}$}$$ = 3,...

The sequence consists of 4 numbers 3, 9, 7, 1 and then it repeats. Now consider the powers of 11:

11, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{11^2}}\right]\kern-.32em\right]}_{20}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{121}}\right]\kern-.32em\right]}_{20}$}$$ = 1, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{11^3}}\right]\kern-.32em\right]}_{20}$}$$ = 11,...

This sequence is periodic of period 2. What about 4? We have

4, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{4^2}}\right]\kern-.32em\right]}_{20}$}$$ = 16, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{4^3}}\right]\kern-.32em\right]}_{20}$}$$ = 4, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{4^4}}\right]\kern-.32em\right]}_{20}$}$$ = 16,...

This is periodic, but the sequence does not contain 1. Finally, let us consider the powers of 6:

6, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{6^2}}\right]\kern-.32em\right]}_{20}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{36}}\right]\kern-.32em\right]}_{20}$}$$ = 16, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{6^3}}\right]\kern-.32em\right]}_{20}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{16\cdot6}}\right]\kern-.32em\right]}_{20}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{96}}\right]\kern-.32em\right]}_{20}$}$$ = 16, $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{6^4}}\right]\kern-.32em\right]}_{20}$}$$ = 16,...

The first two examples give rise to the following definition:

Definition 3.10.6   If there is a positive integer k so that $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^k}}\right]\kern-.32em\right]}_{n}$}$ = 1, we say that a has finite multiplicative order modulo n. The smallest such integer k is called the order of a modulo n.

We can readily categorize the elements with finite order. If you look at the examples above, 3 and 11 have finite order mod 20, while 4 and 6 do not. You probably have already guessed that this is because gcd(3, 20) = 1 and gcd(11, 20) = 1, while gcd(4, 20) = 4 and gcd(6, 20) = 2.

Theorem 3.10.7   Let a and n > 2 be integers. Then a has finite order modulo n if and only if gcd(a, n) = 1.

Proof.  First, suppose a has finite order mod n. Then there is some k so that

1 = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^k}}\right]\kern-.32em\right]}_{n}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a}}\right]\kern-.32em\right]}_{n}$}$$ ^. $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^{k-1}}}\right]\kern-.32em\right]}_{n}$}$$.

Thus, a has a multiplicative inverse, namely $$\left[\vphantom{\kern-.32em\left[{\mystrut{a^{k-1}}}\right]\kern-.32em}\right.$$$$\left[\vphantom{{\mystrut{a^{k-1}}}}\right.$$a^{k - 1}$$\left.\vphantom{{\mystrut{a^{k-1}}}}\right]$$ $$\left.\vphantom{\kern-.32em\left[{\mystrut{a^{k-1}}}\right]\kern-.32em}\right]_{n{^}}^{}$$. By Thm. 10.4, this means gcd(a, n) = 1.

Now we suppose gcd(a, n) = 1, and we want to find the inverse of a. Consider the sequence

a,$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^2}}\right]\kern-.32em\right]}_{n}$}$$,$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^3}}\right]\kern-.32em\right]}_{n}$}$$,...,$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^n}}\right]\kern-.32em\right]}_{n}$}$$,$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^{n+1}}}\right]\kern-.32em\right]}_{n}$}$$.

Since there are n + 1 elements and we are reducing modulo n, there must be at least two which are equal. Let's denote these by $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^k}}\right]\kern-.32em\right]}_{n}$}$ and $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^t}}\right]\kern-.32em\right]}_{n}$}$, with 1$\le$t < k. Since

$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^k}}\right]\kern-.32em\right]}_{n}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^t}}\right]\kern-.32em\right]}_{n}$}$$

we have

$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^{k-t}}}\right]\kern-.32em\right]}_{n}$}$$ = 1.

Thus, a has order k - t mod n. $\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

So, we have seen that any invertible element of $\mbox{${ \mathbb{ Z}}$}$_n has finite order. In particular, if p is a prime number, every element except 0 is invertible and so has finite order. What are the possible orders? A theorem of Pierre de Fermat gives a result in that direction.

Theorem 3.10.8   (Fermat's Little Theorem, 1640)  Let p be a prime. If gcd(a, p) = 1, then

a^{p - 1} $$\equiv$$ 1 mod p.

For any integer a,

a^p $$\equiv$$ a mod p.

Among other things, this theorem says that if p is prime, then the order of a mod p always divides p - 1. Note that it doesn't say the order is p - 1, just that it is a divisor of it. Also, it says nothing about order with modulo a non-prime. We won't give the proof of this theorem here. Rather, we will give a proof of a more general result in the next section.

The Euler $\varphi$-function and Euler's Theorem

Recall that we denote the set of invertible elements of $\mbox{${ \mathbb{ Z}}$}$_n by $\mbox{${ \mathbb{ Z}}$}$_n^*. That is,

$$\mbox{${\mathbb{ Z} }$}$$_n^* = $$\left\{\vphantom{{a \in Z_n \,\,\vrule{}\,\,\gcd(a,n)=1}}\right.$$a $$\in$$ Z_n    gcd(a, n)=1$$\left.\vphantom{{a \in Z_n \,\,\vrule{}\,\,\gcd(a,n)=1}}\right\}$$.

This set is sometimes called a reduced residue system mod n.

Definition 3.10.9   Let n be a positive integer. Then $\varphi$(n) is the number of elements in $\mbox{${ \mathbb{ Z}}$}$_n^*, that is, the number of positive integers less than n which are relatively prime to n. This function is called the Euler $\varphi$-function,^3.23 or sometimes Euler's totient function.

We can compute a few values of $\varphi$(n) just by counting.

$$\varphi$$(2) = 1	since	$$\mbox{${\mathbb{ Z} }$}$$2* = $$\left\{\vphantom{{1}}\right.$$1$$\left.\vphantom{{1}}\right\}$$
$$\varphi$$(3) = 2	since	$$\mbox{${\mathbb{ Z} }$}$$3* = $$\left\{\vphantom{{1,2}}\right.$$1, 2$$\left.\vphantom{{1,2}}\right\}$$
$$\varphi$$(4) = 2	since	$$\mbox{${\mathbb{ Z} }$}$$4* = $$\left\{\vphantom{{1,3}}\right.$$1, 3$$\left.\vphantom{{1,3}}\right\}$$
$$\varphi$$(5) = 4	since	$$\mbox{${\mathbb{ Z} }$}$$5* = $$\left\{\vphantom{{1,2,3,4}}\right.$$1, 2, 3, 4$$\left.\vphantom{{1,2,3,4}}\right\}$$
$$\varphi$$(6) = 2	since	$$\mbox{${\mathbb{ Z} }$}$$6* = $$\left\{\vphantom{{1,5}}\right.$$1, 5$$\left.\vphantom{{1,5}}\right\}$$
$$\varphi$$(7) = 6	since	$$\mbox{${\mathbb{ Z} }$}$$7* = $$\left\{\vphantom{{1,2,3,4,5,6}}\right.$$1, 2, 3, 4, 5, 6$$\left.\vphantom{{1,2,3,4,5,6}}\right\}$$
$$\varphi$$(8) = 4	since	$$\mbox{${\mathbb{ Z} }$}$$8* = $$\left\{\vphantom{{1,3,5,7}}\right.$$1, 3, 5, 7$$\left.\vphantom{{1,3,5,7}}\right\}$$
$$\varphi$$(9) = 6	since	$$\mbox{${\mathbb{ Z} }$}$$9* = $$\left\{\vphantom{{1,2,4,5,7,8}}\right.$$1, 2, 4, 5, 7, 8$$\left.\vphantom{{1,2,4,5,7,8}}\right\}$$
$$\varphi$$(10) = 4	since	$$\mbox{${\mathbb{ Z} }$}$$10* = $$\left\{\vphantom{{1,3,7,9}}\right.$$1, 3, 7, 9$$\left.\vphantom{{1,3,7,9}}\right\}$$
$$\varphi$$(11) = 10	since	$$\mbox{${\mathbb{ Z} }$}$$11* = $$\left\{\vphantom{{1,2,3,4,5,6,7,8,9,10}}\right.$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$$\left.\vphantom{{1,2,3,4,5,6,7,8,9,10}}\right\}$$
$$\varphi$$(12) = 4	since	$$\mbox{${\mathbb{ Z} }$}$$10* = $$\left\{\vphantom{{1,5,7,11}}\right.$$1, 5, 7, 11$$\left.\vphantom{{1,5,7,11}}\right\}$$

Of course, maple also knows about the function $\varphi$ in the numtheory package, so we could generate more values by asking maple. But let's try to understand a bit more. We can readily prove some properties of $\varphi$.

Proposition 3.10.10   Let p$\ge$2 be a prime. Then

a.

$\varphi$(p) = p - 1.

b.

If n is a positive integer, then $\varphi$(pⁿ) = pⁿ - p^{n - 1}.

c.

If a and b are relatively prime, then $\varphi$(ab) = $\varphi$(a)$\varphi$(b).

Proof.  (a) This is immediate, since all non-zero elements of $\left\{\vphantom{{0, 1, \ldots, p-1}}\right.$0, 1,..., p-1$\left.\vphantom{{0, 1, \ldots, p-1}}\right\}$ are invertible.

(b) We prove this part just by counting. Since p is prime, the only numbers in $\mbox{${ \mathbb{ Z}}$}$_p which are not relatively prime to pⁿ are multiples of p. These are 0, p, 2p, 3p,..., p²,(p + 1)p,...,(p^{n - 1} - 1)p. Note that p^{n - 1}p = pⁿ, so there are exactly p^{n - 1} multiples of p less than pⁿ (including 0). All the others are relatively prime to p-- this gives the result.

(c) We need to show that the number of elements in $\mbox{${ \mathbb{ Z}}$}$_ab^* is the same as the product of the size of $\mbox{${ \mathbb{ Z}}$}$_a^* and $\mbox{${ \mathbb{ Z}}$}$_b^*. We do that by showing that for each t $\in$ $\mbox{${ \mathbb{ Z}}$}$_ab^*, there is exactly one pair (r, s) with r $\in$ $\mbox{${ \mathbb{ Z}}$}$_a^*and s $\in$ $\mbox{${ \mathbb{ Z}}$}$_b^*.

So, let r $\in$ $\mbox{${ \mathbb{ Z}}$}$_a^* and s $\in$ $\mbox{${ \mathbb{ Z}}$}$_b^*. Then, by the Chinese Remainder Theorem (Thm. 10.5), there is an integer t < ab with

t $$\equiv$$ r mod a        and        t $$\equiv$$ s mod b.

Since t is a solution of the first, we can find an integer k so that r = t + ka, so gcd(t, a) = gcd(a, r) = 1 by Lemma 10.3. Similarly, gcd(t, b) = 1. Since t is relatively prime to both a and b, it is relatively prime to their product, so gcd(t, ab) = 1. Thus t $\in$ $\mbox{${ \mathbb{ Z}}$}$_ab^*.

Now take t $\in$ $\mbox{${ \mathbb{ Z}}$}$_ab^*, and we must find a corresponding r and s. Let r = $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{t}}\right]\kern-.32em\right]}_{a}$}$. Now, since gcd(t, ab) = 1, certainly gcd(t, a) = 1. Since r $\equiv$ t mod a, there is an integer k so that t = r + ka, so we have gcd(r, a) = 1. Thus r $\in$ $\mbox{${ \mathbb{ Z}}$}$_a^*. Similarly, we let s = $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{t}}\right]\kern-.32em\right]}_{b}$}$, and we see that s $\in$ $\mbox{${ \mathbb{ Z}}$}$_b^*.

Since we have paired each t $\in$ $\mbox{${ \mathbb{ Z}}$}$_ab^* with a unique pair (r, s) $\in$ $\mbox{${ \mathbb{ Z}}$}$_a^* x Z_b^*, they have the same cardinality. The first set has $\varphi$(ab) elements, and the latter has $\varphi$(a)$\varphi$(b). $\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

We now come to Euler's generalization of Fermat's result. This result is the central idea underlying the RSA public key cryptosystem.

Theorem 3.10.11   (Euler, 1750)  Let a and n be relatively prime integers, with n$\ge$2. Then

$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^{\varphi(n)}}}\right]\kern-.32em\right]}_{n}$}$$ = 1.

Proof.  Let a be relatively prime to n, and consider the set

a$$\mbox{${\mathbb{ Z} }$}$$_n^* = $$\left\{\vphantom{{ \mbox{$\displaystyle{\left[\kern-.32em\left[{\... ...rn-.32em\right]}_{n}$} \,\,\vrule{}\,\,b\in\mbox{${\mathbb{ Z} }$}_n^*}}\right.$$$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{ab}}\right]\kern-.32em\right]}_{n}$}$$    b $$\in$$ $$\mbox{${\mathbb{ Z} }$}$$_n^*$$\left.\vphantom{{ \mbox{$\displaystyle{\left[\kern-.32em\left[{\m... ...n-.32em\right]}_{n}$} \,\,\vrule{}\,\,b\in\mbox{${\mathbb{ Z} }$}_n^*}}\right\}$$.

Since a and n are relatively prime, $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a}}\right]\kern-.32em\right]}_{n}$}$ $\in$ $\mbox{${ \mathbb{ Z}}$}$_n^*. Thus every element of a$\mbox{${ \mathbb{ Z}}$}$_n^* is in $\mbox{${ \mathbb{ Z}}$}$_n^*. But also every element of $\mbox{${ \mathbb{ Z}}$}$_n^* is an element of a$\mbox{${ \mathbb{ Z}}$}$_n^*, since $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{ab}}\right]\kern-.32em\right]}_{n}$}$ = $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{ac}}\right]\kern-.32em\right]}_{n}$}$ if and only if $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{b}}\right]\kern-.32em\right]}_{n}$}$ = $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{c}}\right]\kern-.32em\right]}_{n}$}$. This means that the sets a$\mbox{${ \mathbb{ Z}}$}$_n^* and $\mbox{${ \mathbb{ Z}}$}$_n^*are equal.

Now, multiply all the elements of $\mbox{${ \mathbb{ Z}}$}$_n^* together; call the result N. Then $\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{N}}\right]\kern-.32em\right]}_{n}$}$ $\in$ $\mbox{${ \mathbb{ Z}}$}$_n^*. If we multiply all the elements of a$\mbox{${ \mathbb{ Z}}$}$_n^*together, we get a^$\varphi$(n)N, and since the two sets are the same, we have

$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^{\varphi(n)}N}}\right]\kern-.32em\right]}_{n}$}$$ = $$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{N}}\right]\kern-.32em\right]}_{n}$}$$.

Thus,

$$\mbox{$\displaystyle{\left[\kern-.32em\left[{\mystrut{a^{\varphi(n)}}}\right]\kern-.32em\right]}_{n}$}$$ = 1.

$\mbox{\rlap{$\sqcup$ }\raise .2ex\hbox{$\sqcap$ }}$

Footnotes

... $\varphi$-function,^3.23

Although the function was invented by Euler, the notation $\varphi$(n) to represent it is actually due to Gauss.