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$
  • $\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$ – Thomas Andrews Apr 2 '17 at 3:35
  • $\begingroup$ So would that mean this can only hold if $a$ and $b$ are relatively prime? $\endgroup$ – HighSchool15 Apr 2 '17 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$ – Thomas Andrews Apr 2 '17 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$ – darij grinberg Apr 2 '17 at 8:04
  • $\begingroup$ Related : math.stackexchange.com/questions/114841/… $\endgroup$ – lab bhattacharjee Apr 2 '17 at 10:12
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$
  • $\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$ – user 170039 Apr 2 '17 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 '17 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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