Euler phi function

**asub1** · January 21st 2009, 12:43 PM

hi,

I need help
let $gcd(n, m) = 1$ prove that $\phi(nm)=\phi(n)\phi(m)$

thanks

**ThePerfectHacker** · January 21st 2009, 01:52 PM

Originally Posted by asub1

hi,

I need help
let $gcd(n, m) = 1$ prove that $\phi(nm)=\phi(n)\phi(m)$

thanks

Define a function, $\phi : \mathbb{Z}_{nm}^{\times} \to \mathbb{Z}_n^{\times}\times \mathbb{Z}_m^{\times}$ by $\phi ([x]_{nm}) = ([x]_n,[x]_m)$ .
Now argue that this mapping is one-to-one and onto by the Chinese remainder theorem.
And so it follows that $|\mathbb{Z}_{nm}^{\times}| = |\mathbb{Z}_n^{\times}| \times |\mathbb{Z}_m^{\times} | \implies \phi(nm) = \phi(n)\phi(m)$ .

**asub1** · January 22nd 2009, 03:13 AM

Thank you very much!

**asub1** · January 22nd 2009, 03:19 AM

Thank you very much again

Thread: Euler phi function

LinkBack

Thread Tools

Display

Euler phi function

Similar Math Help Forum Discussions

Euler function

Euler Function phi(n)

Euler's phi function

Euler's phi function

Euler phi-Function

Search Tags