- #1

- 42

- 2

## Homework Statement

Suppose m, n are relatively prime. In the problem you will prove the key property of Euler’s function that φ(mn) = φ(m)φ(n).

(a) Prove that for any a, b, there is an x such that

x ##\equiv## a (mod m), (1)

x ##\equiv## b (mod n). (2)

Hint: Congruence (1) holds iff

x = jm + a. (3)

for some j. So there is such an x only if

jm + a ##\equiv## b (mod n). (4)

Solve (4) for j.

(b) Prove that there is an x satisfying the congruences (1) and (2) such that 0 ≤ x < mn.

(c) Prove that the x satisfying part (b) is unique.

(d) For an integer k, let k∗ be the integers between 1 and k − 1 that are relatively prime to k. Conclude from part (c) that the function

f : (mn) ∗ → m∗ × n∗

defined by

f(x) ::= (rem(x, m),rem(x, n))

is a bijection.

(e) Conclude from the preceding parts of this problem that φ(mn) = φ(m)φ(n).

## Homework Equations

Euler's function given at the top:

φ(mn) = φ(m)φ(n)

## The Attempt at a Solution

a) I'm stuck on this first part. Starting by solving (4) for j:

jm + a ##\equiv## b (mod n).

jm ##\equiv## b-a (mod n)

jm = b-a + nl

for some arbitrary l

j= ##\frac{b-a+nl}{m}##

does that constitute solving for j?

if I plug that into

x= jm+a

x= ##\frac{b-a+nl}{m}* m + a##

##=b+nl##

I feel like that's roundabout and doesn't prove that some x exists.

b) I don't know how to get m and n into a relation involving x, other than what was suggested in part a.

x= jm+a

x= ln+b

but that introduces arbitrary variables that I don't know what to do with.

Another option I was considering was letting x= mn+a

so

mn+a ##\equiv## a (mod m)

which would be a valid congruency. But I don't know what to do for the other expression

mn+a ##\equiv## b (mod n)

I will attempt the later parts after I make some progress on these first two.