PlanetMath: Euler phi at a product

(more info)

Math for the people, by the people.

donor list - find out how

Main Menu

Euler phi at a product

(Theorem)

If the positive greatest common divisor of the integers $a$ and $b$ is $d$ , then $$\varphi(ab) = \frac{d\,\varphi(a)\,\varphi(b)}{\varphi(d)}.$$

Proof. Using the positive prime factors $p$ , the right hand side of the asserted equation is

$\displaystyle \frac{d\cdot a\prod_{p\mid a}\frac{p-1}{p}\cdot b\prod_{p\mid b}\frac{p-1}{p}}{d\prod_{p\mid a,\,p\mid b}\frac{p-1}{p}}$	$\displaystyle \;=\; \frac{ab\prod_{p\mid a,\,p\nmid b}\frac{p-1}{p}\cdot\prod_{... ...\prod_{p\mid b,\,p\mid a}\frac{p-1}{p}}{\prod_{p\mid a,\,p\mid b}\frac{p-1}{p}}$
	$\displaystyle \;=\; ab\prod_{p \mid a\;\lor\;p \mid b}\frac{p\!-\!1}{p} \;=\; ab\prod_{p \mid ab}\frac{p\!-\!1}{p} \;=\; \varphi(ab),$

Q.E.D.

"Euler phi at a product" is owned by pahio.

(view preamble | get metadata)

Log in to rate this entry.
(view current ratings)

Cross-references: equation, right hand side, prime factors, proof, integers, greatest common divisor, positive

This is version 2 of Euler phi at a product, born on 2009-05-13, modified 2009-05-13.
Object id is 11779, canonical name is EulerPhiAtAProduct.
Accessed 246 times total.

Classification:

AMS MSC:	11-00 (Number theory :: General reference works )
	11A25 (Number theory :: Elementary number theory :: Arithmetic functions; related numbers; inversion formulas)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact