1. ## Eulers Totient

Hi Guys,

Any information would be great.

φ$\displaystyle (30)$

2. ## Re: Eulers Totient

Originally Posted by extatic
Hi Guys,

Any information would be great.

φ$\displaystyle (30)$
The general expression of Euler's totiens function is...

$\displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

... where $\displaystyle p|n$ means 'prime deviding n'...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

3. ## Re: Eulers Totient

Thank you mate,

Looking at this example, can you tell me how they came to use 2 & 3

$\displaystyle \varphi(36)=\varphi\left(2^2 3^2\right)=36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=36\cdot\frac{1}{2}\cdot\frac{2} {3}=12.$

4. ## Re: Eulers Totient

Originally Posted by chisigma
The general expression of Euler's totiens function is...

$\displaystyle \varphi(n)= n\ \prod_{p|n} (1-\frac{1}{p})$ (1)

... where $\displaystyle p|n$ means 'prime deviding n'...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
Can you check if im correct please,

Since 30 is not prime, we list all of the positive integers less than 30 that are relatively
prime to it:

1, 4, 7, 8, 9, 11 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29.

$\displaystyle \varphi(n)= (30) = 23$

5. ## Re: Eulers Totient

Originally Posted by extatic
Can you check if im correct please,

Since 30 is not prime, we list all of the positive integers less than 30 that are relatively
prime to it:

1, 4, 7, 8, 9, 11 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29.

$\displaystyle \varphi(n)= (30) = 23$
Because 30= 2 x 3 x 5, it is more easy to count the number 1 and all primes greater than 5 and less than 30: 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29... total 8 numbers!...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

6. ## Re: Eulers Totient

So i attempted $\displaystyle \varphi(n)= (10)$

10 = (2 * 5) = 10 * (1 - 1/2)(1 - 1/5)

= 10 * (1/2 * 4/5)

= 4/10 * 10/1

= 4

So there should be 4 prime numbers less than 10 (not including 2 and 5)

1, 3, 7 (only three)

What am i doing wrong?

7. ## Re: Eulers Totient

Originally Posted by extatic
So i attempted $\displaystyle \varphi(n)= (10)$

10 = (2 * 5) = 10 * (1 - 1/2)(1 - 1/5)

= 10 * (1/2 * 4/5)

= 4/10 * 10/1

= 4

So there should be 4 prime numbers less than 10 (not including 2 and 5)

1, 3, 7 (only three)

What am i doing wrong?
In my previous post I have been a little 'approximative'... if n is not prime, i.e. is...

$\displaystyle n= p_{1}^{k_{1}}\ p_{2}^{k_{2}}\ ...\ p_{i}^{k_{i}}$ (1)

... then the totiens function is 1 plus the number of primes p and their powers less than n. In Your case You have 'forgotten' 3 x 3=9...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

8. ## Re: Eulers Totient

by the chinese remainder theorem, if p,q are distinct primes, $\displaystyle \phi(p^rq^s) = \phi(p^r)\phi(q^s)$

thus it suffices to find $\displaystyle \phi(p^r)$, where r is the highest power of p that divides n, for each prime p in the factorization of n.

by counting (never underestimate the power of counting), $\displaystyle \phi(p^r) = (p-1)(p^{r-1})$

so for n = 10, for example, 10 = (2)(5).

φ(2) = 1, φ(5) = 4, so φ(10) = φ(2)φ(5) = (1)(4) = 4.