Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By Petek

Math Help - variation of Euler Totient

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    variation of Euler Totient

    to calculate the number of integers co-prime to N and less than N we can simply calculate its ETF( Euler's totient function - Wikipedia, the free encyclopedia . )However to calculate the number of integers co-prime to N but less then X where X < N , how can we modify / calculate it ? I know how to calcuate the ETF but can't proceed how to modify it to get the required result.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,664
    Thanks
    606

    Re: variation of Euler Totient

    Hey pranay.

    Being co-prime to an integer means the gcd(a,b) = 1.

    But in terms of the totient function, this means that totient(a,b) = totient(a)*totient(b) (which is on the first page of the wiki).

    So you know how many numbers up to n-1 are co-prime by using totient and you also have a condition for when two numbers are co-prime. Can you modify this to get an expression to "remove" the specific numbers of integers that are co-prime but equal or larger than x?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: variation of Euler Totient

    pranay,

    I'm afraid that I don't see how to use chiro's hint. However, your function is very close to what's known as the Legendre Totient Function. It's denoted \phi(X, N) and is defined to be the number of positive integers less than or equal to X that are coprime to N. Your function can be written as \phi(X + 1, N) since you define your function to be the number of integers (positive, I assume) that are less than X and coprime to N. The following formula expresses the Legendre Totient function in terms of the Moebius function \mu and the floor function \lfloor \ \rfloor:

    \phi(X, N) = \sum_{d|N} \mu(d) \left\lfloor\frac{X}{d} \right\rfloor

    where the summation runs over the positive divisors of N. I can provide a proof and/or some references. Just ask or let me know if you have any questions..

    HTH

    Petek
    Thanks from pranay
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2010
    Posts
    95

    Re: variation of Euler Totient

    Thanks a lot Petek, i too got that formula, but could you please explain as to why this works ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18

    Re: variation of Euler Totient

    The formula in my previous post follows from the inclusion-exclusion principle and the observation that the number of positive integers less than or equal to X and divisible by d equals  \left \lfloor \frac{X}{d} \right \rfloor.

    For example, let's compute  \phi(11, 20) :

    The positive divisors of 20 are 1, 2, 4, 5, 10 and 20.

    By direct inspection, the integers 1, 3, 5, 7 and 9 are less than or equal to 11 and coprime to 20, so  \phi(11, 20) = 5.

    The total number of positive integers less than or equal to 11 is  \left \lfloor \frac{11}{1} \right \rfloor = 11.

    From this we have to subtract the number of positive integers less than or equal to 11 that are divisible by 2, which is \left \lfloor \frac{11}{2} \right \rfloor = 5, and the number of positive integers less than or equal to 11 that are divisible by 5, which is \left \lfloor \frac{11}{5} \right \rfloor = 2.

    However, we subtracted the number of positive integers less than or equal 11 that are divisible by 10 twice, so we have to add back  \left \lfloor \frac{11}{10} \right \rfloor = 1.

    Therefore,

    \phi(11, 20) = \left \lfloor \frac{11}{1}  \right \rfloor - \left \lfloor \frac{11}{2} \right \rfloor -  \left  \lfloor  \frac{11}{5} \right \rfloor + \left \lfloor \frac{11}{10} \right \rfloor = 11 - 5 - 2 + 1 = 5,

    where we used  \mu(2) = \mu(5) = -1 and  \mu(10) = 1.

    (Note that \mu(4) = 0, so the term with divisor = 4 doesn't actually appear in the formula. The same is true of the divisor 20, since \mu(20) = 0.)

    Hope you find this explanation useful.
    Last edited by Petek; October 7th 2012 at 04:35 AM. Reason: Add more info
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 30th 2010, 06:21 PM
  2. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: June 3rd 2010, 05:38 PM
  3. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 11th 2009, 04:38 PM
  4. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 29th 2009, 09:46 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 25th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum