mathmari said:
For $n=7$ there are $6$ numbers that have a greatest common divisor of $1$.
So from the Euler's totient function,we have $φ(7)=7(1-\frac{1}{7})=7\frac{6}{7}=6$.
Ok!
- - - Updated - - -
How can I show the first one,that $\phi(mn)=\phi(m)\phi(n)$ ?
Let's ask an easier question, first:
Suppose $p$ and $q$ are primes. Clearly, EVERY positive integer less than $p$ is co-prime to $p$ (that's why we call them primes, right?). A similar assertion hold for $q$, so:
$\phi(p) = p-1$
$\phi(q) = q-1$.
Now, let's consider how many numbers share a common divisor other than 1 with the product $pq$.
Well, clearly, all the multiples:
$p,2p,3p,\dots$ do, and likewise with $q,2q,3q,\dots$.
It's pretty clear that these are all there are for integers $< pq$. Well we can count how many of these there are:
$p,2p,\dots,(q-1)p$ (the next multiple of $p$ is $pq$) for multiples of $p$, and:
$q,2q,\dots,(p-1)q$ for multiples of $q$.
So we have $q-1$ multiples of $p$ we have to "subtract out" from the $pq - 1$ positive integers less than $pq$, and $p-1$ multiples of $q$ to subtract out, as well.
So: $\phi(pq) = pq - 1 - (p-1) - (q-1) = pq - 1 - p + 1 - q + 1 = pq - p - q + 1$
$= pq - (p+q) + 1 = (p - 1)(q - 1) = \phi(p)\phi(q)$.
Now, it's actually easier to show next that if: $n = p^k$ then:
$\phi(n) = p^{k-1}(p -1)$
Suppose $\text{gcd}(m,p^k) = d > 1$. Clearly $d$ is of the form $p^t$ for some $0 < t \leq k$, and $p$ divides every single one of these.
On the other hand, it should be clear that every multiple of $p$ up to (but not including) $p^{k-1}p$ has such a common factor, and we can count these multiples of $p$:
$p,2p,\dots,p^2,(p^2+1)p,\dots,p^3,\dots,(p^{k-1} - 1)p$, so there are:
$p^{k-1} - 1$ integers less than $p^k$ that are NOT co-prime to $p^k$, and this is all of them.
Hence:
$\phi(p^k) = p^k - 1 - (p^{k-1} - 1) = p^k - p^{k-1} = p^{k-1}(p - 1)$.
So, what is there left to show? Well, we haven't covered every possible integer, yet.
Use what I have above, to show that:
$\phi(p^kq^m) = \phi(p^k)\phi(q^m)$ (just two prime factors).
(Hint: if $n = p^kq^m$ show that if $\text{gcd}(r,n) \neq 1$, either $p|r$ or $q|r$. Count the multiples of $p$ and the multiples of $q$, and subtract the ones you've "double-counted" (the multiples of $pq$)).
Now use induction on the number of primes in any factorization of $n$ to get a general formula (use a similar "counting trick").
**********
On a slightly different tack, it turns out this result is actually equivalent to the Chinese Remainder Theorem, which may be more accessible to you (depending on your mathematical background), often stated in the form:
$U(\Bbb Z_m \times \Bbb Z_n) \cong U(\Bbb Z_m) \times U(\Bbb Z_n)$
**********
Small correction:
The actual formula is:
$\displaystyle \phi(n) = n\prod_{p|n} \left(1 - \frac{1}{p}\right)$.
This seems a lot less mysterious when you realize:
$p^{k-1}(p-1) = p^k\left(1 - \dfrac{1}{p}\right)$
so you put all the prime factors of $n$ outside the $\prod$ sign (together, they multiply up to...$n$), and all the:
$\left(1 - \dfrac{1}{p}\right)$
factors inside the "giant product".
