Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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............. – Un Chien Andalou Jul 28 '13 at 15:46
in 2nd link what is $m\perp n$? – Un Chien Andalou 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
up vote 1 down vote accepted

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)$.

share|cite|improve this answer

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".

share|cite|improve this answer

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)].

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.