Loading ...
Sorry, an error occurred while loading the content.
 

Re: I find it very interesting...

Expand Messages
  • djbroadhurst
    ... You may find this useful: phi(a*b)=phi(a)*phi(b)*g/phi(g), where g=gcd(a,b). David
    Message 1 of 6 , Jun 1, 2013
      --- In primenumbers@yahoogroups.com,
      "leavemsg1" <leavemsg1@...> wrote:

      > I wondered about the "algebra" of Euler's phi function

      You may find this useful:
      phi(a*b)=phi(a)*phi(b)*g/phi(g), where g=gcd(a,b).

      David
    • Mohsen Afshin
      That surely derives from the fact that if both n-k and n+k are primes then phi(n^2-k^2) = phi((n-k)(n+k)) = phi(n-k) * phi (n+k) = (n-k-1) * (n+k-1) = n^2 - 2n
      Message 2 of 6 , Jun 1, 2013
        That surely derives from the fact that if both n-k and n+k are primes then

        phi(n^2-k^2) = phi((n-k)(n+k)) = phi(n-k) * phi (n+k) = (n-k-1) * (n+k-1) =
        n^2 - 2n + 1 - k^2 = (n-1)^2 - k^2
        Example
        n = 105, k = 4

        phi(105^2-4^2) = (105-1)^2 - 4^2 = 10800 = (101-1)*(109-1)

        But my question is how we can approach to an additive feature of EulerPhi?

        If there was one such a feature then the primality tests would become so
        easy. As an example consider n!+1, we know phi(n!) without any computation
        and using that dreamed feature we could easily check if phi(n!+1) equals n!
        or not :-)

        I already tried some here
        http://math.stackexchange.com/questions/249982/how-to-calculate-euler-totient-from-nearby-values


        On Sat, Jun 1, 2013 at 4:11 PM, djbroadhurst <d.broadhurst@...>wrote:

        > **
        >
        >
        > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...> wrote:
        >
        > > phi(n^2-k^2) = (n-1)^2 - k^2, working for ONLY some n's and some k's
        >
        > Let n and k be positive integers with n > k+1. Then
        > eulerphi(n^2-k^2) = (n-1)^2 - k^2
        > if and only if n+k and n-k are both prime.
        >
        > David
        >
        >
        >



        --
        "Mathematics is the queen of the sciences and number theory is the queen of
        mathematics."
        --Gauss


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.