# multiplicative Euler's $\phi$ function

Here is the pdf and array

I am not understanding the proof that $\phi$ is multiplicative function i.e for relatively prime $m,n$ we have $\phi(mn)=\phi(m)\phi(n)$

There were Three Lemmas before the proving original Theorem which I understood

$L_1: a \text{ is prime to } mn \Leftrightarrow(a,m)=1,(a,n)=1$

$L_2: a=qn+r, (r,n)=1 \text{ Then} (a,n)=1$

$L_3:$ If $c$ be the integer and $(a,n)=1$ Then the number of integers in the set $\{c,c+a,c+2a,\dots,c+(n-1)a\}$ that are prime to $n$ is $\phi(n)$

Then they arranged $mn$ integers in $n$ rows and $m$ collumns , I have not understood this arrangement and based on this arrangements the proof. could any one help me understand?

-
To calculate $\phi(m\cdot n)$ we need to check for integers from $1$ to $m\cdot n,$ right? –  lab bhattacharjee Jul 28 '13 at 15:44
yes............. –  La Belle Noiseuse Jul 28 '13 at 15:46
in 2nd link what is $m\perp n$? –  La Belle Noiseuse Jul 28 '13 at 15:47
@TaxiDriver Thanks for the accept! Let me know if anything needs to be cleared out. But... no upvote? =) –  Pedro Tamaroff Jul 29 '13 at 17:33

I hope the following makes the claim as clear as possible:

THM Assume that $(a,b)=1$. Then $$(a,x)=1 \text{ and } (b,y)=1\iff (ax+by,ab)=1$$

P We prove the contrapositive of each direction.

$(\Rightarrow)$ Suppose thus that there is a prime $p$ such that $p\mid (ax+by,ab)$. Then $p\mid ab$. Without loss of generality, assume $p \mid a$. Since $p\mid ax+by$, we have $p\mid by$, and since $(a,b)=1$, $p\mid y$. Thus $p\mid (a,y)\implies (a,y)>1$. We have thus proven, under the hypothesis that $(a,b)=1$; that $$(ax+by,ab)>1\implies (a,y)>1 \text{ or } (b,x)>1$$ since the other option would have been assuming that $p\mid a$.

$(\Leftarrow)$ Now suppose $(x,b)>1$. Then $(ax+by,ab)>1$ since $(x,b)\mid ax+by$. Analogously, $(a,y)>1$ implies $(ax+by,ab)>1$. $\blacktriangle$

COR Suppose that $(a,b)=1$, and that $x$ ranges through the $\phi(b)$ numbers coprime to $b$ and $y$ ranges throughout the $\phi(a)$ numbers coprime to $a$. Then $ax+by$ ranges throughout the $\phi(a)\cdot\phi(b)$ numbers coprime to $ab$, which in turn is $\phi(a\cdot b)$.

-

The best thing you can do, is trying it yourself on an example..

You arrange the numbers to the rows, since in each row there are $\Phi(m)$ nubers $a$ which you take in account (i.e. $gcd(m,a) = 1$) and the position of such nubers are always the same in tha rows (so they make a column) and the difference of two nubers in the same column is necessarilly a multiple of $m$. Then you do the reasoning of the forth article, which says in fact the same but for columns.

The general idea is: "write the numbers $\leq mn$ in that matrix and clear the columns in which the numbers have a $gcd$ with $m$ greater than $1$ and with the rest do the same for rows; you must have left $\Phi(m)$ rows and $\Phi(n)$ columns, so at the end you finish with $\Phi(m)\Phi(n)$ numbers; the fact that $gcd(m,n)=1$ ensures that when deleting columns you have not deleted some numbers you would want to delete in the second step".

-

As in a previously posted answer, there are only $\phi (m)$ columns that consist of elements relatively prime to mn. This follows from the fact that if $(km+r,mn)=1$, then $(km+r,m)=1$ by Lemma 1 and so $(r,m)=1$ since $(km+r,m)=(r,m)$. Then each of these columns contains $\phi (n)$ elements relatively prime to n by Lemma 3, and these elements are relatively prime to mn as well by Lemma 1.

[Another way to prove this fact is to map each integer k in {1,...,mn} which is relatively prime to mn to $(r_1,r_2)$, where $r_1$ and $r_2$ are the remainders when k is divided by m and n, respectively. Using Lemma 1, $r_1$ and $r_2$ are relatively prime to m and n; and this mapping is 1-1 (since (m,n)=1) and onto (by the Chinese Remainder Theorem)].

-