What can we say about \(\varphi (mn) \) for \(m\) and \(n\) in general?

By -
In class we proved that if \(m\) and \(n\) are coprimes (i.e. \(gcd(m,n)=1\)),  then \(\varphi(mn) = \varphi(m)\varphi(n)\).

In this article we will discuss what will happen for \(m\) and \(n\) in general. In other words, given \(gcd(m,n)=d\) for some \(d\in\mathbb{N}\), what can we say about \(\varphi(mn)\)?

Let's first do prime factorization for both \(m\) and \(n\), then
$$m = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$$
$$n = q_1^{r_1}q_2^{r_2}...q_j^{r_j}$$

Consider \(gcd(m,n)=d \geq 2\). Then \(m\) and \(n\) have at least one common prime factors. Assume the prime factorization expressions for \(m\) and \(n\) above are written in the way that \(m\) and \(n\)'s common prime factors are written at the beginning and aligned correspondingly. i.e. \(p_i = q_i\) for all \(1\leq i \leq c\) for some \(c\leq min(j,k)\). Then we can say the prime factors for \(m\) and \(n\)'s common divisor, \(d\), are \(p_i\)'s where  \(1\leq i \leq c\).

Then
$$\begin{eqnarray}
\varphi(mn) &=& mn(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_c})[(1-\frac{1}{p_{c+1}})...(1-\frac{1}{p_k})][(1-\frac{1}{q_{c+1}})...(1-\frac{1}{q_j})]\\
&=&\frac{\varphi(m)\cdot\varphi(n)}{(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_c})}\\
&=&\frac{\varphi(m)\cdot\varphi(n)}{\varphi(d)/d}\\
&=&\frac{\varphi(m)\varphi(n)d}{\varphi(d)}
\end{eqnarray}
$$

Finally let's verify whether this equation, \(\varphi(mn)=\frac{\varphi(m)\varphi(n)d}{\varphi(d)}\), also holds for \(d=1\). When \(d=1\), \(\varphi(d)=\varphi(1)=1\). So the equation will give us \(\varphi(mn)=\frac{\varphi(m)\varphi(n)\cdot 1}{1}\), which we already proved to be true.

Therefore we can conclude that, if \(gcd(m,n)=d\), then  \(\varphi(mn)=\frac{\varphi(m)\varphi(n)d}{\varphi(d)}\).

Comments

Post a Comment

Popular posts from this blog

Common counting techniques

By Natasha -
Image
Before we go too far with proving various clever binomial coefficient identities, let's try counting some things with them. Stars and bars We know that there are " n  choose  k " ways to pick  k  children out of a group of  n  children (assuming we can tell the children apart). But what if we add an indistinguishable element to the story? Unlike our distinguishable children, let's say we have some identical candies to hand out. One natural question is: How many ways are there to hand out  k  indistinguishable candies to  n  distinguishable children? Here's where the stars and bars come in. Let's say we have 3 children and 8 candies. We can think of the candies as the "stars." The 3 children can be thought of as candy receptacles (sorry, kids), distinguished only by their order from left to right. So here's one way we could distribute the candy: ***|****|* In this case, the first child/candy receptacle gets 3 candies, the second gets 4
Read more

"Pyramid Numbers" Fun Fact!

By -
Similar to the set up for the triangular numbers, "pyramid number," or \(P_n\), refers to the required number of dots for a \(n\) triangular base pyramid that has \(n\) dots per side on its base. And here is a fun fact for \(P_n\): $$\sum_{n=1}^{\infty}{\frac{1}{P_n}} = \frac{3}{2}$$ To prove this equality, we first may need some kind of formula for \(P_n\) so that we can do something with the LHS. As you may have found in homework, "Pyramid numbers" are a series of numbers right next to "triangular numbers" in Pascal's triangle. Therefore we know a general formula for \(P_n\): $$P_n = {n+2\choose 3} = \frac{(n+2)\cdot (n+1)\cdot n}{3!}$$ Now, we can rewrite the LHS and try to split the sum expression: $$\begin{eqnarray} \sum_{n=1}^{\infty}{\frac{1}{P_n}} &=& \sum_{n=1}^{\infty}{\frac{1}{(\frac{(n+2)\cdot (n+1)\cdot n}{3!})}}\\ &=&3!\sum_{n=1}^{\infty}{\frac{1}{(n+2)\cdot (n+1)\cdot n}}\\ &=&3!(\frac{1}{1\cdot 2 \cd
Read more

Parallelogram Identity Proof (Using Stars and Bars Technique)

By -
The parallelogram identity in Pascal's triangle states that, given an entry \({n \choose k}\) in Pascal's triangle, \({n \choose k}-1 = \) the sum of the entries included in the rectangle that is straight above entry \({n \choose k}\) and also includes the apex of Pascal's triangle. This equality can be expressed as a double sum as follows, $${n+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{n-k}{n-i-j \choose k-i}$$.  We can prove this by using the stars and bars technique that we are familiar with. For easier explanation, let's first rewrite the double sum expression above in another form (but mathematically equivalent). Set \(r = n-k\), we have  $${r+k+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i}$$.  Let's assume we have \((k+1)\) stars and \(r\) bars. As we have already known, \({r+k+1 \choose k+1}\) counts the number of different star-bar sequences. This implies that maybe we can try to interpret the RHS as another way to count almo
Read more