That is,

why is $\varphi(AB)=\varphi(A)\varphi(B)$, if $A$ and $B$ are two coprime positive integers?

It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its multiplicativity should be an approximation at most. And why the minimum value for $\varphi (n)$ should be $ \frac{4n}{15} $ completely passes me by.

  • 7
    $\begingroup$ @Chris: It’s multiplicative in the usual number-theoretic sense: if $m$ and $n$ are relatively prime, $\varphi(mn)=\varphi(m)\varphi(n)$. $\endgroup$ Commented Sep 7, 2012 at 17:44
  • 6
    $\begingroup$ Hint: Think chinese remainder theorem. If $a,b$ are relatively prime, then $\gcd(n,ab)=1$ if and only if $\gcd(n,a)=\gcd(n,b)=1$ $\endgroup$ Commented Sep 7, 2012 at 17:44
  • $\begingroup$ So what does that line upload.wikimedia.org/wikipedia/commons/4/48/EulerPhi100.PNG represent? An approximation for the minimum with small n? $\endgroup$
    – Meow
    Commented Sep 7, 2012 at 17:50
  • $\begingroup$ @Alyosha It represent the fact that the totient is more than $4n/15$ for $n=1,...,100$ $\endgroup$ Commented Sep 7, 2012 at 17:52
  • 1
    $\begingroup$ Heres a proof: math.wisc.edu/~josizemore/Notes11%28phi%29.pdf Perhaps you should elaborate what approach your textbook is using $\endgroup$
    – flawr
    Commented Sep 3, 2014 at 10:39

15 Answers 15


In general, if $R$ and $S$ are rings, then $R\times S$ is a ring. The units of $R\times S$ are the elements $(r,s)$ with $r$ a unit of $R$ and $s$ a unit of $S$. If $R$ and $S$ are finite rings, the number of units in $R\times S$ is therefore the number of units in $R$ times the number of units in $S$.

Now if $\gcd(A,B)=1$, then $$\mathbb Z/\left<AB\right> \cong \mathbb Z/\left<A\right> \times \mathbb Z/\left<B\right>$$

This is essentially the Chinese remainder theorem.

But the number of units in the ring $\mathbb Z/\left<n\right>$ is $\phi(n)$. So the number of units in $\mathbb Z/\left<AB\right>$ is $\phi(AB)$ and the number of units in $\mathbb Z/\left<A\right> \times \mathbb Z/\left<B\right>$ is $\phi(A)\phi(B)$

  • 1
    $\begingroup$ I'm not sure why I accepted this answer, I have no background in rings. Can you point me to a source (on the internet, ideally) using which I could understand this answer? [sorry for reposting, tried to un-outedit the @ Thomas Andrews] $\endgroup$
    – Meow
    Commented Feb 2, 2013 at 20:26
  • 1
    $\begingroup$ Can you prove this using only the Chinese Remainder Theorem? I don't think there's a need to resort to rings. Many of the people finding this answer on google will be lowly computer scientists with no knowledge of rings but need the totient function for use in asymmetric encryption. $\endgroup$ Commented Feb 12, 2013 at 18:11
  • 1
    $\begingroup$ Yeah, I wouldn't have picked this as the best answer, either, because it is fairly abstract. I just wanted to add the argument because it clarifies things for a lot of people, but, as you say, it probably obscures more than it clarifies for beginners. $\endgroup$ Commented Feb 12, 2013 at 19:16
  • 1
    $\begingroup$ @ThomasAndrews So you mean that $\mathbb{Z}_{nm} \cong \mathbb{Z}_n \times \mathbb{Z}_m $. And this, implies that the unit elements in $\mathbb{Z}_{nm}$, will be again units in the isomorphic ring $\mathbb{Z}_n \times \mathbb{Z}_m $. So, $|U(\mathbb{Z}_{nm})| = |U(\mathbb{Z}_n)|| U( \mathbb{Z}_m) |$. Right? And, can we say that $U(\mathbb{Z}_{nm}) \cong U(\mathbb{Z}_n) \times U(\mathbb{Z}_m) $? And if yes, why? $\endgroup$
    – Chris
    Commented Nov 22, 2016 at 2:17
  • $\begingroup$ @Chris I know it's a bit late, but: simply because the operations on the Cartesian product are define component-wise. This means that the product of two elements $(a_1,b_1),(a_2,b_2) \in \Bbb{Z}_n \times \Bbb{Z}_m$ is, by definition, $(a_1a_2,b_1b_2)$. Then $(1,1)$ is the identity and $(a,b)$ is a unit if and only if $a$ and $b$ are units in $\Bbb{Z}_n$ and $\Bbb{Z}_m$, respectively. This actually holds for the product of any two rings $R \times S$ and it's pretty straightforward to prove (I basically did it just now). $\endgroup$
    – A.P.
    Commented Jan 23, 2018 at 22:18

$$n = \prod_{k=1}^{z}p_{k}^{e_{k}}$$ $$\varphi(n) = n \prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$ Let $$a=\prod_{k=1}^{w} p_{k}^{e_{k}}\quad b=\prod_{k=w+1}^{z} p_{k}^{e_{k}}$$ $n=ab$, then $$\varphi(a) = a\prod_{k=1}^{w}(1-\frac{1}{p_{k}})$$ $$\varphi(b) = b\prod_{k=w+1}^{z}(1-\frac{1}{p_{k}})$$ $$\varphi(a)\varphi(b) = ab\prod_{k=1}^{w}(1-\frac{1}{p_{k}}) \cdot \prod_{k=w+1}^{z}(1-\frac{1}{p_{k}})$$ $$=ab\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$ $$=n\prod_{k=1}^{z}(1-\frac{1}{p_{k}})$$ $$=\varphi(n)$$ $$\varphi(a)\varphi(b)=\varphi(ab)$$

  • 2
    $\begingroup$ @CheltonEvans If both accounts that edited this question (Chelton Evans and Chelton) belong to you, you might try to merge them as described here. $\endgroup$ Commented Nov 28, 2013 at 9:25

THM Assume that $(a,b)=1$. Then $$(a,y)=1 \text{ and } (b,x)=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)$.

  • 3
    $\begingroup$ I think the proof of your corollary needs an extra explanation. When $x$ and $y$ range through the numbers coprime to $b$ and $a$ respectively, the sum $ax+by$ may be bigger than $ab$. You use that two such sums are always distinct when considered modulo $ab$. However you are using the Chinese Remainder Theorem here implicitly, is that right? (I posted the same comment some minutes ago and then deleted it again) $\endgroup$ Commented May 18, 2017 at 20:27
  • $\begingroup$ A missing element in the corollary is that we need to somehow show that the correspondence between the LHS and the RHS in the theorem itself is a bijection. This can be fixed by finding $a a' = 1$ (mod $b$) and $b b' = 1$ (mod $a$), which is doable because $(a,b)=1$, and replacing $ax+by$ by $a a' x + b b' y$ in the theorem. The bijection part is then a direct consequence of the CRT. See this link. $\endgroup$ Commented Mar 18, 2022 at 20:10

First of all $\phi(mn)=\phi(m)\times \phi(n)$ is only true if $m$ and $n$ are coprime.

We can prove this using the chinese remainder theorem.

Let $M$ be the set of numbers smaller than $m$ that are coprime to $m$ and let $N$ be the set of numbers smaller than $n$ that are coprime to $n$

By definition $\phi(m) = |M|$ and $\phi(n) = |N|$

if $m$ and $n$ are coprime it follows from the chinese remainder theorem that there are |$N|\times |M|$ numbers that are coprimes of $mn$ smaller than $mn$

The chinese remainder theorem states that there is a bijection between $\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$ and $\mathbb{Z}/nm\mathbb{Z}$. We use this bijection to send $(a,b)$ with $a<n$ and $b <m$ to a $c$ with $c<nm$ , $c \equiv a \mod n$ and $c \equiv b \mod m$.

If $a$ is coprime to $n$ and $b$ is coprime to $m$ this bijection sends $(a,b)$ to $c$ with $c$ coprime to $nm$.(Because c has no divisor in common with n or m) Therefore there is a bijection between $N \times M$ and the numbers coprime to $mn$ smaller than $nm$.

Thus $\phi(mn) = |M| \times |N| = \phi(m)\times \phi(n)$

  • 1
    $\begingroup$ That looks really great! I'll review chinese remainder theorem quick and get back thank you so much :) $\endgroup$
    – rrr
    Commented Sep 3, 2014 at 11:29
  • $\begingroup$ I tried to explain it with some more detail. $\endgroup$ Commented Sep 3, 2014 at 12:17
  • $\begingroup$ Do you know about this? $\endgroup$
    – user170039
    Commented Sep 3, 2014 at 13:18
  • $\begingroup$ No i didn't, is there a connection with this? $\endgroup$ Commented Sep 3, 2014 at 13:55

This just addresses the erroneous notion that $\frac{\varphi(n)}n$ has a positive lower bound, but it’s too long for a comment.

If $m_n=p_1\dots p_n$ is the product of the first $n$ primes, then $\varphi(m_n)=\prod\limits_{k=1}^np_k\left(1-\frac1{p_k}\right)$, and $$\frac{\varphi(m_n)}{m_n}=\prod_{k=1}^n\left(1-\frac1{p_k}\right)\;.$$

Consider the reciprocal,

$$\begin{align*} \frac{m_n}{\varphi(m_n)}&=\prod_{k=1}^n\left(\frac1{1-p_k^{-1}}\right)\\ &=\prod_{k=1}^n\sum_{i\ge 0}\frac1{p_k^i}\\ &\ge\prod_{k=1}^n\left(1+\frac1{p_k}\right)\;. \end{align*}$$

For positive $a_k$ the infinite product $\prod_{k\ge 1}(1+a_k)$ converges iff the series $\sum_{k\ge 1}a_k$ converges, and it’s well known that $\sum_{k\ge 1}\frac1{p_k}$ diverges, so $\lim_{n\to\infty}\frac{m_n}{\varphi(m_n)}\to\infty$, and therefore $\lim_{n\to\infty}\frac{\varphi(m_n)}{m_n}=0$.

  • $\begingroup$ Why is the convergence of that product equivalent to that of the sum? $\endgroup$ Commented Apr 26, 2017 at 16:14

If $\phi(n)$ is the Euler's Totient Function, then the proof goes as follows :

By definition $\phi(p)=p-1$ if p is prime,

Now, if $n$ is any composite number, then $n=pq$, where $p$ and $q$ are prime.

To see that $\phi(n)=\phi(p)\times \phi(q)$, consider that the set of positive integers less than $n$ is the set $\{1,.....(pq-1)\}$. The integers in this set that are not relatively prime to $n$ are the set $\{p,2p,....(q-1)p\}$and the set $\{q,2q,....(p-1)q\}$. Accordingly

Then $\phi(n)=\phi(pq)=pq-1-[(q-1)+(p-1)]=pq-(p+q)+1=(p-1)(q-1)=\phi(p)\phi(q)$ as required . $\square$

  • 26
    $\begingroup$ Not every composite number is a product of 2 primes. So you didn't prove for the most general case. $\endgroup$ Commented Sep 3, 2014 at 10:53
  • $\begingroup$ Clever! I see now, this does helps me in comprehending the general proof :) Is there any assumption in your proof that $q <p$ ? $\endgroup$
    – rrr
    Commented Sep 3, 2014 at 10:59
  • 4
    $\begingroup$ This proof is not good as $\phi(4) \neq \phi(2)\times\phi(2)$. You need the extra condition that $m$ and $n$ are relatively prime $\endgroup$ Commented Sep 3, 2014 at 11:02
  • $\begingroup$ I see... this method seems way more intuitive and simpler to me. I think it should work for all square free integers atleast ? $\endgroup$
    – rrr
    Commented Sep 3, 2014 at 11:05
  • $\begingroup$ @user172209 Do you know the chinese remainder theorem? There is an easy proof using that. $\endgroup$ Commented Sep 3, 2014 at 11:11

In general, you're right that $\Phi(AB)\neq\Phi(A)\Phi(B)$--for example, $\Phi(8)=4$, but $\Phi(2)=1$ and $\Phi(4)=2$. At best, we can usually only say that $\Phi(AB)\geq\Phi(A)\Phi(B)$. We will have equality when (and only when) $A,B$ are coprime, though.

Let $R_1,R_2$ be rings, and note that $R_1\times R_2$ is also a ring with componentwise addition and multiplication. A given $(x_1,x_2)\in R_1\times R_2$ has a multiplicative inverse if and only if the $x_k$ have multiplicative inverses in $R_k$.

Note that integers $A,B$ are coprime if and only if there exist integers $X,Y$ such that $AX+BY=1$ if and only if $A$ has a multiplicative inverse modulo $B$ and $B$ has one modulo $A$. Thus, there are precisely $\Phi(A)$ elements of $\Bbb Z/A\Bbb Z$ having multiplicative inverse.

By the above discussion, $\Bbb Z/AB\Bbb Z$ will have $\Phi(AB)$ elements with multiplicative inverses, and $(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$ will have $\Phi(A)\Phi(B)$ such elements.

The only thing left to prove is that there is a bijection (in fact, an isomorphism) between $\Bbb Z/AB\Bbb Z$ and $(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$. That $A,B$ are coprime is crucial to the proof, so be sure you use it! I'd start with the natural homomorphism $\Bbb Z\to(\Bbb Z/A\Bbb Z)\times(\Bbb Z/B\Bbb Z)$ given by $X\mapsto(X\,mod\, A,X\, mod\, B)$, which readily has kernel $AB\Bbb Z$, and then use the coprimality of $A,B$ to show surjectivity, so the desired conclusion follows by First Isomorphism Theorem.

Edit: Your addendum is incorrect. The $\frac{4n}{15}$ lower bound is obtained when we're looking at the first $100$ values of $\Phi(n)$--attained by $30,60,90$, but it is misleading. There are numbers beyond it that fall below that bound, such as $210$. There is in fact no lower bounding straight line of positive slope through the origin that applies to all the integers.


If $n=p_1^{a_1}p_2^{a^2} \dots p_r^{a_r}$ with the $p_i$ distinct primes (eg in increasing order to get a canonical form) and the $a_i$ positive integers, then we have:$$\phi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dots\left(1-\frac1{p_r}\right)$$ (worth working out for yourself) - then if $m$ and $n$ are co-prime they bring in different factors for their respective prime divisors and the multiplicativity is easy to see. If you bear in mind that the sum of the reciprocals of primes is unbounded, you will be able to see that you can make the prime bit of the product as small as you like (eg take logs), so that $\frac{\phi(n)}n$ can be made as small as possible. You will even be able to choose values of $n$ which make this fraction particularly small. I mention this expression for $\phi(n)$ because it is the one which has most aided my intuition.

  • $\begingroup$ Thank you- at long last it's clicked! $\endgroup$
    – Meow
    Commented Apr 2, 2013 at 19:14

An “abstract” proof using some group theory. Note that $\phi(mn)=\phi(m)\phi(n)$ only holds if $m$ and $n$ are coprime, so we assume this throughout.

The Chinese remainder theorem can be seen as a proof that, if $m$ and $n$ are coprime, then $\def\Z{\mathbb{Z}}\Z/m\Z\times \Z/n\Z$ is cyclic. Let $$ \sigma\colon\Z\to\Z/m\Z\times \Z/n\Z, \sigma(k)=(k+m\Z,k+n\Z) $$ The kernel of $\sigma$ is $m\Z\cap n\Z=t\Z$ where $t$ is the lowest common multiple of $m$ and $n$; since $m$ and $n$ are coprime, $t=mn$. Therefore $\sigma$ induces an injective homomorphism $$ \bar{\sigma}\colon \Z/(mn)\Z\to\Z/m\Z\times \Z/n\Z $$ which, by cardinality reasons is also surjective. This proves the Chinese remainder theorem.

Let $\psi=\bar{\sigma}^{-1}$ be the inverse of $\bar{\sigma}$.

Let now $G_1$ and $G_2$ be cyclic groups of orders $m$ and $n$ respectively. If $x$ and $y$ are generators respectively of $G_1$ and $G_2$, then $(x,y)$ is a generator of the (cyclic) group $G_1\times G_2$. Indeed, we have an isomorphism $\gamma_1\colon G_1\to\Z/m\Z$ such that $\gamma_1(x)=1+m\Z$ and, similarly, an isomorphism $\gamma_2\colon G_1\to\Z/n\Z$ such that $\gamma_2(x)=1+n\Z$.

Setting $\beta(g_1,g_2)=\psi(\gamma_1(g_1),\gamma_2(g_2))$ defines an isomorphism $G_1\times G_2\to\Z/(mn)\Z$ that sends $(x,y)$ to $1+(mn)\Z$. Therefore $(x,y)$ is a generator of $G_1\times G_2$.

Conversely, it's easy to see that if $(x,y)$ is a generator of $G_1\times G_2$, then $x$ is a generator of $G_1$ and $y$ is a generator of $G_2$.

Now, $\phi(m)$ is exactly the number of elements in $\Z/m\Z$ that are generators (why?). Therefore, by the argument above $$ \phi(mn)=\phi(m)\phi(n) $$ because the choice of a generator of $\Z/(mn)\Z$ corresponds to the choice of a generator of $\Z/m\Z$ and a generator of $\Z/n\Z$.


The reason for the result follows from the property of primes that if $p\mid mn$ then $p\mid m$ or $p\mid n$. Since $\gcd(m,n)=1$, $p\mid mn$ implies that $p$ divides exactly one of them (not both).

Therefore, if we want to look at the primes dividing $mn$ we can first look at the primes dividing $m$, then look at the primes dividing $n$.

Remember that $\phi(n)=n\prod_{p\mid n}(1-\frac{1}{p})$. If $\gcd(m,n)=1$ then $\prod_{p\mid mn}(1-\frac{1}{p})=(\prod_{p\mid m}(1-\frac{1}{p}))(\prod_{p\mid n}(1-\frac{1}{p}))$.

This is equivalent to $\frac{\phi(mn)}{mn}=\frac{\phi(m)}{m}\cdot\frac{\phi(n)}{n}$, or $\phi(mn)=\phi(m)\phi(n)$.


Möbius inversion can provide a neat proof:

$$ \sum_{d|n}\mu(d)= \begin{cases} 1 & n=1 \\ 0 & n>1 \end{cases} $$

By definition, we have

\begin{aligned} \varphi(n) &=\sum_{\substack{1\le k\le n\\(k,n)=1}}1=\sum_{1\le k\le n}\sum_{d|(k,n)}\mu(d) \\ &=\sum_{d|n}\mu(d)\sum_{\substack{1\le k\le n\\d|k}}1=\sum_{d|n}\mu(d)\frac nd \\ &=n\sum_{d|n}{\mu(d)\over d} \end{aligned}

Since $\mu(d)/d$ is multiplicative w.r.t $d$, it follows from the properties of Dirichlet convolutions that $\varphi(n)$ is also multiplicative.


First let's show that $$\phi(mp^l) = \phi(m)\phi(p^l),$$ where $p$ is a prime number and $m,p$ are coprime.

Let $$S = \{x|gcd(x,mp^l)=1 \: \& \: x\leq mp^l \},$$ and $$S_1 =\{x|gcd(x,m)=1 \: \& \: x\leq mp^l \},$$

We can easily see that $S \subset S_1$ (why? verify!).

The cardinality of $S_1$, i.e., $|S_1| = \phi(m)p^l$ (why? hint: each element in $S_1$ is of form $km + b$, $k\in\mathbb{N}$, where, $b\leq m$ and $gcd(m,b)=1$).

Now let's ask which elements of $S_1$ have a non trivial common divisor with $mp^l$. These are exactly of the form of $kp$, $k\in \mathbb{N}$. (why? verify!)

Let's investigate this form, i.e., $kp$.

$kp \in S_1$ implies $kp$ is coprime with $m$, which in turn implies $k$ is coprime with $m$ (why? verify!).

Since $kp \leq mp^l$

$k \leq mp^{l-1}$

Thus, number of elements of $S_1$, which are not coprime with $mp^l$ is $\phi(m)p^{l-1}$.

Thus, $$\phi(mp^l) = \phi(m)p^l - \phi(m)p^{l-1} = \phi(m)(p^l - p^{l-1})$$

You can verify that $\phi(p^l) = p^l - p^{l-1}$.

Hence, $$\phi(mp^l) = \phi(m) \phi(p^l). $$

From this it is easy to show that $$\phi(mn) = \phi(m)\phi(n)$$ when $m \: \& \:n$ are coprime.

(hint: use prime factorization of $n$).


If you already know the formula $$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$$ then the rest is easy.

(The above formula can be shown using principle of inclusion and exclusion.)

However, many texts prove first that $\varphi$ is multiplicative and then use this fact to derive the above formula.


$gcd(m, n)=1 \Rightarrow \phi(mn) = \phi(m) \cdot \phi(n)$

The following proof requires neither group theory nor explicit use of the Chinese Remainder Theorem, but it's analogous to some of the above:

Consider the reduced residue system (RRS) modulo $mn$:
$R = \{r : 1 \leq r \leq mn\}$. Then $|R|=\phi(mn)$
And consider the complete residue systems modulo $m$ and $n$:
$A' = \{1, 2, ... m\}$ $B' = \{1, 2, ... n\}$
Now let $S'=A' \times B'$
This is a Cartesian product consisting of the set of all ordered pairs $(a \mod m, b \mod n)$
Now consider the reduced residue systems mod $m$ and $n$, and their Cartesian product:
$A = \{a : a=gcd(a,m)\}$. Then $|A|=\phi(m)$
$B = \{b : b=gcd(n,n)\}$. Then $|B|=\phi(n)$
$S=A \times B$, so $|S| = \phi(m) \cdot \phi(n)$
And clearly, $S \subseteq S'$

The proof requires showing that $R$ and $S$ are bijective, i.e., $R \leftrightarrow S$
$\Rightarrow: \; \forall r \in R$ there exists a unique ordered pair in $S$
Existence is shown by construction: $gcd(x, y)$ is defined for any $x, y $ not both $0$.
Uniqueness can be shown by contraposition:
Assume for $i \neq j, \; r_i, \; r_j \in R$ both map to the same ordered pair in $S'$
Then $r_i \equiv r_j \mod m$ and $r_i \equiv r_j \mod n$
So $m \mid (r_i-r_j)$ and $n \mid (r_i-r_j)$
But since $gcd(m, n)=1, \; mn \mid (r_i-r_j)$
Hence, $r_i=r_j$, which is a contradiction
And if $r$ maps uniquely to $S'$, then it maps uniquely to $S$

$\Leftarrow: \; \forall (a,b) \in S $ there is a unique $r \in R$
To show this, solve the following system of congruences:
$(1) \; r \equiv a \mod m$
$(2) \; r \equiv b \mod n$
From (1), $r=mx+a$
Substituting into (2), $mx+a \equiv b \mod n$
Or $ (3) \; mx - ny = a-b$
Since $gcd(m, n)=1 $, the solutions for (3) are given by $(x_0-\frac{nk}{1}, \; y_0 - \frac{mk}{1}) \; \forall k \in \mathbb{Z}$
The solutions for $r$ are thus given by $mx_0-mnk+a = (mx_0+a) - mnk$
But $R$ is a complete residue system modulo mn
Thus, there is only one and only one such solution in $R \;\; \square$


$gcd(m, n)=1 \Rightarrow \phi(mn) = \phi(m) \cdot \phi(n)$
To prove this let's assume a function $f:N \implies N$
$f(m)=number\ of\ integers\ (i)\ less\ than\ or\ equal\ to\ m\ and\ gcd(m,i) > 1 $
Now, $ϕ(m)=m-f(m)$
Same way, $ϕ(n)=n-f(n)$
Now, $f(mn)=|M|+|N|-|M \cap N| $
Here, $M=\{i|\ i<mn\ and\ gcd(m,i)>1\}.$
Hence, $|M|=nf(m)$, Since we are counting all the integer multiples of first $f(m)$ numbers in $N$ which are not relatively prime with $m$ and which are less then or equal to $mn$.
And same way, $|N|=mf(n)$
Now, $|M \cap N|=f(m)f(n)$, Since $m$ and $n$ are relatively prime and we are counting all the numbers which are not relatively prime with any of this numbers and are less than or equal to $mn$.
Now, $\phi(mn)=mn-f(mn)$
Hence proved!


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .