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

Thread: 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
    6,598
    Thanks
    1712

    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 $\displaystyle \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 $\displaystyle \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 $\displaystyle \mu$ and the floor function $\displaystyle \lfloor \ \rfloor$:

    $\displaystyle \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 $\displaystyle \left \lfloor \frac{X}{d} \right \rfloor$.

    For example, let's compute $\displaystyle \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 $\displaystyle \phi(11, 20) = 5$.

    The total number of positive integers less than or equal to 11 is $\displaystyle \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 $\displaystyle \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 $\displaystyle \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 $\displaystyle \left \lfloor \frac{11}{10} \right \rfloor = 1$.

    Therefore,

    $\displaystyle \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 $\displaystyle \mu(2) = \mu(5) = -1 $ and $\displaystyle \mu(10) = 1$.

    (Note that $\displaystyle \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 $\displaystyle \mu(20) = 0$.)

    Hope you find this explanation useful.
    Last edited by Petek; Oct 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: Jun 30th 2010, 06:21 PM
  2. Euler Totient Function
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Jun 3rd 2010, 05:38 PM
  3. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Oct 11th 2009, 04:38 PM
  4. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jan 29th 2009, 09:46 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Mar 25th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum