Thread: Eulers Totient

Hi Guys,

Any information would be great.

φ

Originally Posted by extatic

Hi Guys,

Any information would be great.

φ

The general expression of Euler's totiens function is...

(1)

... where means 'prime deviding n'...

Kind regards

Thank you mate,

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

Originally Posted by chisigma

The general expression of Euler's totiens function is...

(1)

... where means 'prime deviding n'...

Kind regards

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.

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.

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

So i attempted

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?

Originally Posted by extatic

So i attempted

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...

(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

by the chinese remainder theorem, if p,q are distinct primes,

thus it suffices to find , 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),

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

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