Lagranges Theorem

• Aug 31st 2008, 03:47 PM
particlejohn
Lagranges Theorem
So we have $\phi(n) = \prod_{i=1}^{k} \phi(p_{i}^{e_{i}}) = \prod_{i=1}^{k} p_{i}^{e_{i}-1}(p_{i}-1)$. So basically what it is saying that the number of numbers coprime to $n$ is equal to the totient product of their prime factors. So then $\phi(8) = 4 \neq \phi(2) \cdot \phi(2) \cdot \phi(2)$. What's wrong with this (am I interpreting this incorrectly)? Also why is $\phi(n)$ defined for integers $\leq n$ as opposed to just integers $< n$. Because a number is never coprime with itself right?
• Aug 31st 2008, 03:54 PM
ThePerfectHacker
Quote:

Originally Posted by particlejohn
Also why is $\phi(n)$ defined for integers $\leq n$ as opposed to just integers $< n$. Because a number is never coprime with itself right?

You are right. It makes no difference.
I would guess is the problem with $n=1$.
Since the set $\{ 1\leq x < n\}$ would be empty.
And then $\phi(1) = 0$.
But we want to define it as $\phi(1)=1$.
• Aug 31st 2008, 03:54 PM
particlejohn
Sorry I am using Lagrange's Theorem, but the above is not Lagrange's Theorem.
• Aug 31st 2008, 05:11 PM
particlejohn
But $\phi(8) = 4 \neq \phi(2) \times \phi(2) \times \phi(2) = 1$. Or does it mean $\phi(2^{3})$?
• Aug 31st 2008, 05:16 PM
ThePerfectHacker
Quote:

Originally Posted by particlejohn
But $\phi(8) = 4 \neq \phi(2) \times \phi(2) \times \phi(2) = 1$.

That is wrong!
The rule $\phi(ab)=\phi(a)\phi (b)$ holds when $\gcd(a,b)=1$.
• Aug 31st 2008, 10:39 PM
particlejohn
Quote:

Originally Posted by particlejohn
So we have $\phi(n) = \prod_{i=1}^{k} \phi(p_{i}^{e_{i}}) = \prod_{i=1}^{k} p_{i}^{e_{i}-1}(p_{i}-1)$. So basically what it is saying that the number of numbers coprime to $n$ is equal to the totient product of their prime factors. So then $\phi(8) = 4 \neq \phi(2) \cdot \phi(2) \cdot \phi(2)$. What's wrong with this (am I interpreting this incorrectly)? Also why is $\phi(n)$ defined for integers $\leq n$ as opposed to just integers $< n$. Because a number is never coprime with itself right?

Ok this is for distinct prime factors. $8 = 2^{3}$ which is not distinct prime factors.
• Sep 1st 2008, 12:05 AM
Moo
Hello,

Another formula is :

$\phi(n)=n \prod_{i=1}^k \left(1-\frac{1}{p_i}\right)$

where $p_i$ is a prime divisor of n.

For example, $140=2^2 \cdot 5 \cdot 7$
$p_1=2 ~,~ p_2=5 ~,~ p_3=7$