Mon, Mar 3

```The Euler Phi-Function Is Multiplicative
(3/3)
• Last time we showed that if p is prime, then
•
•
•
•
•
•
(pk) = pk – pk-1 .
Hence by the FTA, we will be able to compute (m) for
any m provided that is multiplicative (recall that
definition!).
To this end, let m and n be relatively prime. We define two
sets:
Let S = {a : 1 ≤ a ≤ mn and GCD(a, mn) = 1}.
How elements does S have?
Let T = {(b, c) : 1 ≤ b ≤ m and GCD(b, m) = 1, and
1 ≤ c ≤ n and GCD(c, n) = 1}.
How many elements does T have?
Do S and T have the same number
of elements?
• We will know then that
(mn) = (m) (n) if we can show
that S and T have the same number of elements. We can
do that by displaying a one-to-one and onto
correspondence between the two sets.
(This is basic set theory.)
• Okay, so let f be the function from S to T given by
f (a) = (a (mod m), a (mod n)).
• Example: Suppose m = 8, n = 7, and a = 25. Then
f (a) = (?, ?).
• We claim f is one-to-one and onto.
The function f is one-to-one
• We show “one-to-oneness” of a function by assuming that
there are two elements of the domain which are sent to the
same element of the range, and show that they were in fact
• So assume a1 and a2 are in S, and suppose f (a1) = f (a2),
i.e., a1 (mod m) = a2 (mod m) and a1 (mod n) = a2 (mod n).
• Hence m | (a2 – a1) and n | (a2 – a1), but then, by Exercise
7.2 (which you did!), we get that ……..
• Thus a1 = a2 (why?), and so we have established that f is
one-to-one.
The function f is onto
• This is trickier. In fact this result is itself an important one
in number theory and hence has its own name:
• The Chinese Remainder Theorem. If GCD(m, n) = 1, then
the simultaneous congruences
x b (mod m) and x c (mod n)
have a unique solution x1 with 0 ≤ x1 < mn.
• This is best seen via an example. Suppose again that
m = 8 and n = 7. What is a solution less than 56 to to the
congruences x 1 (mod 8) and x 4 (mod 7)?
• Well, we already saw that 25 is a solution. This theorem
(CRT) says it will be only solution as well.
An algorithm to solve simultaneous
congruences
• Consider again x
1 (mod 8) and x 4 (mod 7).
What’s x (below 56)?
• Since x
1 (mod 8) , we know there exists a y such that
x = 1 + 8y. Plug this into the second congruence:
1 + 8y 4 (mod 7), so 8y 3 (mod 7).
• But we know that since GCD(7, 8) = 1, this linear
congruence has a unique solution! Using our EEA
algorithm to solve it (or by reducing the 8 (mod 7)!),
we get y = 3. Hence x = 1 + 8(3) = 25, as predicted!
• Why is 25 unique? Well, y was unique below 7, but then x
had to be unique and at most 7 + 8(6) = 55.