2
$\begingroup$

Prove $\varphi(a)\varphi(b)=\varphi(\gcd(a,b))\varphi(\operatorname{lcm}[a,b])$

I know $ab=\gcd(a,b)\operatorname{lcm}[a,b]$.

Let $d = \gcd(a,b)$ and $\ell=\operatorname{lcm}(a,b)$. Notice that $\frac{ab}{d}$ is a common multiple of $a$ and $b$, since $\frac{a}{d}$ and $\frac{b}{d}$ are integers, by definition. By Euclidean algorithm, $\frac{a}{d}$, $\frac{b}{d}$ are relatively prime. Now assume n is common multiple of $a$ and $b$, then we can find integers $k$ and $k'$ such that $n=ka$ and $n=k'b$ so $ka=k'b$. We divide both sides by $d$ (we remain in integers!) to get $k'\frac{b}{d} =k\frac{a}{d}$. $\frac{a}{d}$ divides $\frac{b}{d} k'$ and since $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime then $\frac{a}{d}$ divides $k'$. Hence $n=k'b=q\frac{ab}{d}$ for some integer q. So $\frac{ab}{d} $ divides $n$. Hence $\operatorname{lcm}(a,b) =\frac{ab}{\gcd(a,b)}$ or $\operatorname{lcm}(a,b)\gcd(a,b)=ab$

SoI would like to show $\varphi(ab)=\varphi(\operatorname{lcm}(a,b)\gcd(a,b))=\varphi(\gcd(a,b))\varphi(\operatorname{lcm}[a,b])$

$\endgroup$
5
  • $\begingroup$ Assuming $\phi$ is Euler's phi function, it is not true in general that $\phi(ab)=\phi(a)\phi(b)$. That is only true if $a,b$ are relatively prime. $\endgroup$ Apr 2, 2017 at 3:35
  • $\begingroup$ So would that mean this can only hold if $a$ and $b$ are relatively prime? $\endgroup$ Apr 2, 2017 at 3:38
  • $\begingroup$ No, the theorem you are trying to prove is true for all $a,b$. The thing you claimed to know is not true, so don't use it. $\endgroup$ Apr 2, 2017 at 3:42
  • 1
    $\begingroup$ Note that this equality holds not merely for the totient function $\varphi$, but for any multiplicative number-theoretic function instead. I find this interesting, as I've never seen this identity before, but it's listed on the Wikipedia page! $\endgroup$ Apr 2, 2017 at 8:04
  • $\begingroup$ Related : math.stackexchange.com/questions/114841/… $\endgroup$ Apr 2, 2017 at 10:12

3 Answers 3

1
$\begingroup$

This solution uses the fundamental theorem of arithmetic. Let's write $$a=p_1^{r_1}\cdots p_n^{r_n},$$ $$b=p_1^{s_1}\cdots p_n^{s_n}.$$

where the $p_i$'s are prime numbers and $r_1,\ldots r_n,s_1\ldots s_n\ge 0$. Then by a well-known formula we have $$\phi(a)=p_1^{r_1-1}(p_1-1)\cdots p_n^{r_n-1}(p_n-1),$$ $$\phi(b)=p_1^{s_1-1}(p_1-1)\cdots p_n^{s_n-1}(p_n-1).$$

Thus $\phi(a)\phi(b)=p_1^{r_1+s_1-2}(p_1-1)^2\cdots p_n^{r_n+s_n-2}(p_n-1)^2.$

On the other hand, we have that $$\gcd(a,b)=p_1^{\min\{r_1,s_1\}}\cdots p_n^{\min\{r_n,s_n\}},$$ $$\text{lcm}(a,b)=p_1^{\max\{r_1,s_1\}}\cdots p_n^{\max\{r_n,s_n\}}.$$

Therefore $$\phi(\gcd(a,b))=p_1^{\min\{r_1,s_1\}-1}(p_1-1)\cdots p_n^{\min\{r_n,s_n\}-1}(p_n-1),$$ $$\phi(\text{lcm}(a,b))=p_1^{\max\{r_1,s_1\}-1}(p_1-1)\cdots p_n^{\max\{r_n,s_n\}-1}(p_n-1).$$

Then $$\phi(\gcd(a,b))\phi(\text{lcm}(a,b))=p_1^{\min\{r_1,s_1\}+\max\{r_1,s_1\}-2}(p_1-1)^2\cdots p_n^{\min\{r_n,s_n\}+\max\{r_n,s_n\}-2}(p_n-1)^2.$$

Finally, as $r_i+s_i-2=\min\{r_i,s_i\}+\max\{r_i,s_i\}-2$ for every $1\le i\le n$, we conclude that $$\phi(a)\phi(b)=\phi(\gcd(a,b))\phi(\text{lcm}[a,b]).$$

$\endgroup$
2
  • $\begingroup$ If $s_1=0$ then in the formula for $\varphi(b)$ how can we write, $\varphi(b)=\color{red}{p_1^{s_1-1}}\ldots p_n^{s_n-1}(p_n-1)$? $\endgroup$
    – user170039
    Apr 2, 2017 at 13:31
  • 1
    $\begingroup$ @user170039 just don't count it. Note also that in this case $\min\{r_1,s_1\}=0$, so $p_1$ doesn't appear in $\gcd(a,b)$ and thus $\phi(a)\phi(b)=p_1^{r_1-1}\cdots$ and $\phi(\gcd(a,b))\phi(\text{lcm}(a,b))=p_1^{r_1-1}\cdots$. $\endgroup$
    – Xam
    Apr 2, 2017 at 16:06
1
$\begingroup$

With the convention that the product of the members of the empty set is $1$:

Let $P(n)$ be the set of prime divisors of $n$. Then $\phi (n)=n\cdot\prod_{p\in P(n)}(p-1)/p.$

Let $A=P(a)\cap P(b)$ and $Q(a)=P(a)$ \ $A$ and $Q(b)=P(b)$ \ $A$. Note that these sets are pair-wise disjoint.

We have $\phi(a)=$ $a\cdot\prod_{p\in A}(p-1)/p\cdot \prod_{p\in Q(a)}(p-1)/p.$

We have $\phi(b)=$ $b\cdot \prod_{p\in A}(p-1)/p\cdot \prod_{p\in Q(b)}(p-1)/p.$

Therefore $$\bullet \quad\phi(a)\phi(b)=ab\cdot\prod_{p\in A}(p-1)^2/p^2\cdot\prod_{p\in Q(a)}(p-1)/p\cdot\prod_{p\in Q(b)}(p-1)/p.$$

Now $P(\gcd(a,b))=P(a)\cup P(b)$ and $ P(lcm(a,b))=$ $P(a)\cup P(b)=$ $A\cup Q(a)\cup Q(b).$

$$\text {So } \quad \phi (\gcd(a,b))=\gcd(a,b)\cdot\prod_{p\in A}(p-1)/p.$$

$$ \text {And }\quad \phi(lcm(a,b))=lcm (a,b)\cdot \prod_{p\in P(a)\cup P(b)}(p-1)/p=$$ $$=lcm (a,b)\cdot \prod_{p\in A}(p-1)/p\cdot \prod_{p\in Q(a)}(p-1)/p\cdot \prod_{p\in Q(b)}(p-1)/p.$$

Therefore $$ \bullet \bullet \quad \phi(\gcd(a,b))\cdot \phi(lcm(a,b))=$$ $$= \gcd(a,b)\cdot lcm(a,b)\cdot \prod_{p\in A}(p-1)^2/p^2\cdot \prod_{p\in Q(a)}(p-1)/p\cdot\prod_{p\in Q(b)}(p-1)/p.$$

Combining $\bullet$ and $\bullet \bullet$ we have $$\frac {\phi(\gcd (a,b))\cdot \phi (lcm(a,b))}{\phi(a)\cdot \phi(b)}=\frac {\gcd(a,b)\cdot lcm(a,b)}{ab}=1.$$

$\endgroup$
0
$\begingroup$

Hint: It seems straightforward using the following explicit formula: $$\phi(n) = n\prod_{p|n}(1-\dfrac{1}{p}).$$

Also use that if $p_1,p_2,..p_k$ are the common prime factors of $a$ and $b$, with respective orders $\alpha_k$ and $\beta_k$, then $lcm(a,b) = \prod_{i=1}^kp_i^{\max(\alpha_i, \beta_i)}$ and $gcd(a,b) = \prod_{i=1}^kp_i^{\min(\alpha_i, \beta_i)}$.

$\endgroup$

You must log in to answer this question.

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