Euler's Totient Function, Proof

[QuietMind]

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.

 

[haruspex]

What do you know about the existence of inverses modulo a prime?

 

[QuietMind]

So I looked around and found a very similar problem, with a different hint (note that this variant swaps a,b with m,n).

part a) For a and b relatively prime,
$x \equiv m mod a$
$x \equiv n mod b$
They said to let
$b^-1$
be inverse of
$b mod a$
and $a-1$ be inverse of
$a mod b$

let
$x = mbb^-1 + naa^-1$

which satisfies both congruences.

ie.

$x = mbb^-1 + naa^-1 \equiv m (mod a)$
$mbb^-1 \equiv m (mod a) That hint leads me down a very different path than the original hint for part a. How did you know that multiplicative inverses were needed? b)I'm not sure how to start the second part of the original problem. Do I have to prove that$x \equiv rem(x, ab) mod ab##

and redefine x as the remainder term?

 

[haruspex]

For now, I'm just going to clean up your Latex to make it readable:

So I looked around and found a very similar problem, with a different hint (note that this variant swaps a,b with m,n).

part a) For a and b relatively prime,
$x \equiv m \mod a$
$x \equiv n \mod b$
They said to let $b^{-1}$ be inverse of $b \mod a$ and $a^{-1}$ be inverse of $a \mod b$
let $x = mbb^{-1} + naa^{-1}$
which satisfies both congruences.

ie. $x = mbb^{-1} + naa^{-1} \equiv m (\mod a)$
$mbb^{-1} \equiv m (\mod a)$
That hint leads me down a very different path than the original hint for part a. How did you know that multiplicative inverses were needed?

b)I'm not sure how to start the second part of the original problem. Do I have to prove that
$x \equiv rem(x, ab) \mod ab$

and redefine x as the remainder term?

If there is going to be a solution for x in the range 0 to ab-1, what does that suggest about how the solutions are distributed? If a given x is one solution, where might the next solution be?

 

[QuietMind]

Oh, I'm sorry about messing up the LaTeX. Sorry, I was in a hurry, I'll be sure to double-check in the future.

If given x is a solution, I would think more solutions can be expressed as x+abk, where k is an arbitrary integer. The abk would be canceled by the modulus operator.
So then by part a, we know that there is some solution x that is not necessarily in the specified range. Then by adding or subtracting abk for some k, there will certainly be a congruent solution in the range $0 \leq x\lt ab$
Otherwise, if some solution x was greater than ab, but the next solution below it is less than 0, this would lead to a contradiction
$x\geq ab$
$x-ab\lt0$

c)
Of the set of solutions that are expressed as
$x+akb$
there can only be one solution in the range of 0 to ab.

So then we have to account for the possibility that some y, which not congruent to x, is also a solution.
Say
$y \equiv m$ (mod a)
$y \equiv n$ (mod b)
then by transitivity
$y \equiv x$ (mod a)
$y \equiv x$(mod b)

so then by the definition of congruency
$a \mid (y-x)$
$b \mid (y-x)$
a and b are relatively prime, so the difference (y-x) must contain their prime factorizations with no overlap (Unique Factorization Theorem)
This means
$ab \mid (y-x)$
which implies
$y \equiv x$ (mod ab)
which means it's impossible for the two not to be congruent. They would have the same congruent solution in the range 0 to ab.

d) I am going to revert back to using the m,n and a,b as stated in the original problem.
By the Unique Factorization Theorem, a number is relatively prime to mn iff it is relatively prime to both m and n.

So the function f maps a value x to the pair (x mod m, x mod n)
By parts b and c, we know that we can select x to be congruent to any (a mod m, b mod n) (in this problem we want a, b not equal to 0.)
and that this x will be unique (because it is on the limited range 0 to mn-1). So this means the function is a surjection and injection. I don't know how to prove that it is total... I think I'd have to prove the domain and range have the same cardinality, at which point surjection implies total function. How would I go about doing that?

e) if the function from d) is a bijection, well then
the cardinality of (mn)* must be equal to the cardinality of (m*)x(n*),
which is essentially the definition of $\phi(n)$

 

[haruspex]

I would think more solutions can be expressed as x+abk

So would I, but you need to prove it. If x is a solution, show that x+ab is a solution.

the function is a surjection and injection.

And hence a bijection, no?

 

[QuietMind]

if x is a solution to
$x \equiv m$ (mod a)
$x \equiv n$ (mod b)

then x+abk
$x+abk \equiv x \equiv m$ (mod a)
$x+abk \equiv x \equiv n$ (mod b)

And hence a bijection, no?

I thought you needed to show that a function is surjective, injective and total? Otherwise, couldn't you have something like
A= (1,2,3)
B=(4,5)
f: A -> B
f(1)=4
f(2)=5
with f(3) not mapping onto anything. Isn't this surjective and injective, but not bijective?

 

[haruspex]

I thought you needed to show that a function is surjective, injective and total? Otherwise, couldn't you have something like
A= (1,2,3)
B=(4,5)
f: A -> B
f(1)=4
f(2)=5
with f(3) not mapping onto anything. Isn't this surjective and injective, but not bijective?

As far as I am aware, a function, not qualified as being partial, is necessarily total. I.e. totality is implied unless specifically stated otherwise.

 

[QuietMind]

I see, thanks. Did the rest of my solution make sense- I mean the parts that you did not specifically address?

 

[haruspex]

I see, thanks. Did the rest of my solution make sense- I mean the parts that you did not specifically address?

Yes, all else looked good.