# Math Help - Proof about Euler's φ-function

1. ## Proof about Euler's φ-function

Prove that if m,n are positive integers with (m,n)=1, then φ(m.n) = φ(m)φ(n).

I was told to use the Chinese Remainder Theorem to show that wach pair of elements [a]n & [a]m (in Zm, Zn respectively) corresponds to a unique element [x]mn in Zmn. Then show that this correspondence, [a] & [b] are units if and only if [x] is a unit.

2. In general is...

$\displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

... so that if m and n have no common prime factors is...

$\displaystyle \varphi(m\ n)= m\ \prod_{p|m} (1-\frac{1}{p})\ n\ \prod_{p|n} (1-\frac{1}{p})= \varphi(m)\ \varphi(n)$ (2)

Kind regards

$\chi$ $\sigma$

3. Originally Posted by page929
Prove that if m,n are positive integers with (m,n)=1, then φ(m.n) = φ(m)φ(n).

I was told to use the Chinese Remainder Theorem to show that wach pair of elements [a]n & [a]m (in Zm, Zn respectively) corresponds to a unique element [x]mn in Zmn. Then show that this correspondence, [a] & [b] are units if and only if [x] is a unit.
I assume your [a]m was supposed to be [b]m? I think the hint is almost a proof in itself! Where are you stuck?

4. Originally Posted by chisigma
In general is...

$\displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

I don't think they can use this...in fact, as far as I remember, to reach this formula one must first know the multiplicativity of $\phi$ and its values on powers of primes.
If they ould use this formula the question would be utterly trivial

Tonio

... so that if m and n have no common prime factors is...

$\displaystyle \varphi(m\ n)= m\ \prod_{p|m} (1-\frac{1}{p})\ n\ \prod_{p|n} (1-\frac{1}{p})= \varphi(m)\ \varphi(n)$ (2)

Kind regards

$\chi$ $\sigma$
.

5. In ...

Totient Function -- from Wolfram MathWorld

... is written the following precedure...

... the 'fundamental theorem of arythmetic' extablishes that any integer $m>1$ is represented as the product...

$\displaystyle m= \prod_{k=1}^{r} p_{k}^{\alpha_{k}}$ (1)

... where $p_{k} , k=1,2,...,r$ are the r distincts primes deviding m. If $m= p^{\alpha}$ the numbers of factors relatively prime to m is...

$\displaystyle \varphi (m) = p^{\alpha}\ (1-\frac{1}{p})$ (2)

If $m= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}}$ the numbers of factors relative prime to m is...

$\displaystyle \varphi (m) = p_{1}^{\alpha_{1}}\ (1-\frac{1}{p_{1}})\ p_{2}^{\alpha_{2}}\ (1-\frac{1}{p_{2}}) = m\ (1-\frac{1}{p_{1}})\ (1-\frac{1}{p_{2}})$ (3)

Proceeding by induction we arrive at the formula...

$\displaystyle \varphi(m)= m\ \prod_{k=1}^{r} (1-\frac{1}{p_{k}})$ (4)

It is remarkable the fact that the (4) has beeen derived only from (1) [i.e. the fundamental theorem of arithmetic...] without any other hypothesis, so that the formula valid for m and n coprimes...

$\varphi(m\ n) = \varphi (m)\ \varphi (n)$ (5)

... is derived from (4) and not viceversa...

Kind regards

$\chi$ $\sigma$

6. Originally Posted by chisigma
In ...

Totient Function -- from Wolfram MathWorld

... is written the following precedure...

... the 'fundamental theorem of arythmetic' extablishes that any integer $m>1$ is represented as the product...

$\displaystyle m= \prod_{k=1}^{r} p_{k}^{\alpha_{k}}$ (1)

... where $p_{k} , k=1,2,...,r$ are the r distincts primes deviding m. If $m= p^{\alpha}$ the numbers of factors relatively prime to m is...

$\displaystyle \varphi (m) = p^{\alpha}\ (1-\frac{1}{p})$ (2)

If $m= p_{1}^{\alpha_{1}}\ p_{2}^{\alpha_{2}}$ the numbers of factors relative prime to m is...

$\displaystyle \varphi (m) = p_{1}^{\alpha_{1}}\ (1-\frac{1}{p_{1}})\ p_{2}^{\alpha_{2}}\ (1-\frac{1}{p_{2}}) = m\ (1-\frac{1}{p_{1}})\ (1-\frac{1}{p_{2}})$ (3)

Proceeding by induction we arrive at the formula...

$\displaystyle \varphi(m)= m\ \prod_{k=1}^{r} (1-\frac{1}{p_{k}})$ (4)

It is remarkable the fact that the (4) has beeen derived only from (1) [i.e. the fundamental theorem of arithmetic...] without any other hypothesis

This is interesting and I wasn't aware of it, but it isn't completely accurate: only in point (13) arrives Wolfram to the formula, after having used induction and, in (6)-(7)-(8) using a not so straightforward deduction on different primes dividing a given natural number n.

Anyway, is another way to approach this.

Tonio

, so that the formula valid for m and n coprimes...

$\varphi(m\ n) = \varphi (m)\ \varphi (n)$ (5)

... is derived from (4) and not viceversa...

Kind regards

$\chi$ $\sigma$
.