0

Let $a, b\in \mathbb{N}$, with $a\perp b$.

Define $S_{ab}=\{m\in\mathbb{N}\ |\ m<ab, m\perp ab\}$, $S_a=\{m\in\mathbb{N}\ |\ m<ab, m\perp a\}$, and $S_b=\{m\in\mathbb{N}\ |\ m<ab, m\perp b\}$. Define a function $f:S_{ab}\to S_a\times S_b$ by $f(x)=(x\mod a, x\mod b)$. Show that this is well-defined and bijective to prove that $\varphi(ab)=\varphi(a)\varphi(b)$.

I got stuck on the existence part of the well defined function proof, and I'm sure uniqueness and surjectivity might cause me more struggles. I guess for existence, it would be sufficient to show that $(x\mod a) \perp a$, but I'm not sure how to proceed.

user10448599
  • 137

1 Answers1

1

By definition, to show the the existence part, we need to prove that for any $x\in S_{ab}$, $f(x)=(x\mod a, x\mod b)$ is an element of $S_a\times S_b$. That is, $x\mod a\in S_a$ and $x\mod b\in S_b$. This is ture because $x\in S_{ab}$ means $x\perp ab$, so $ x\perp a$. Let $s=(x\mod a)$, then we just need to prove $s\perp a$ (The proof of mod b part is similar). Because $s=(x\mod a)$, there exist an integer $t$, such that $s=x-ta$. Assuming $s$ is not coprime to $a $, then there exist an integer $q\ge 2 $, such that $q|a$ and $q|s$, then $q|(s+t\cdot a)=x$. Then $x$ and $a$ are not coprime ($q$ divides them), a contradiction! So the assuming is wrong, that is $s\perp a$.

The uniqueness part is because if $f(x)=f(y)$, then $x\mod a $ = $ y\mod a$, so $a|(x-y)$. Similarly, $b|(x-y)$. But $a\perp b$, so $ab|(x-y)$. Recall $0<x,y<ab$ we get x=y, showing the uniqueness part.

The surjectivity part follows from Bezout's Theorem plus a little trick, you can try it.

Bonbon
  • 891