# Lagranges Theorem

• Aug 31st 2008, 02:47 PM
particlejohn
Lagranges Theorem
So we have $\displaystyle \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 $\displaystyle n$ is equal to the totient product of their prime factors. So then $\displaystyle \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 $\displaystyle \phi(n)$ defined for integers $\displaystyle \leq n$ as opposed to just integers $\displaystyle < n$. Because a number is never coprime with itself right?
• Aug 31st 2008, 02:54 PM
ThePerfectHacker
Quote:

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

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

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

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

Originally Posted by particlejohn
So we have $\displaystyle \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 $\displaystyle n$ is equal to the totient product of their prime factors. So then $\displaystyle \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 $\displaystyle \phi(n)$ defined for integers $\displaystyle \leq n$ as opposed to just integers $\displaystyle < n$. Because a number is never coprime with itself right?

Ok this is for distinct prime factors. $\displaystyle 8 = 2^{3}$ which is not distinct prime factors.
• Aug 31st 2008, 11:05 PM
Moo
Hello,

Another formula is :

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

where $\displaystyle p_i$ is a prime divisor of n.

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