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

Re: [PrimeNumbers] Prime formula...

Expand Messages
  • Jud McCranie
    ... One direction is trivial, I think the other one is easy too.
    Message 1 of 4 , May 3, 2004
    • 0 Attachment
      At 01:29 PM 5/3/2004, William Bouris wrote:
      >Hello Group...
      >
      >Can someone prove or disprove?
      >
      >phi( (p^2) ) = [phi(p)]^2 + phi(p) iff "p" is prime, and phi(...) is the
      >totient function.
      >
      >Or is this equation already known?


      One direction is trivial, I think the other one is easy too.
    • Andrew Swallow
      ... phi(n^2)=n*phi(n), for any n. so boils down to showing that phi(n)=n-1 iff n is prime. which is easily known. Andy
      Message 2 of 4 , May 3, 2004
      • 0 Attachment
        > phi( (p^2) ) = [phi(p)]^2 + phi(p) iff "p" is prime,
        > and phi(...) is the totient function.
        >
        > Or is this equation already known? Bill.


        phi(n^2)=n*phi(n), for any n. so boils down to showing
        that phi(n)=n-1 iff n is prime. which is easily known.

        Andy





        ____________________________________________________________
        Yahoo! Messenger - Communicate instantly..."Ping"
        your friends today! Download Messenger Now
        http://uk.messenger.yahoo.com/download/index.html
      • Shiv Nandan Singh
        phi(p^2) = p*( p-1)......(1) phi(p)=p-1..........(2) Using 1 and 2 in phi( (p^2) ) = [phi(p)]^2 + phi(p) we get p*(p-1) = (p-1)^2 + p-1 I think the result is
        Message 3 of 4 , May 3, 2004
        • 0 Attachment
          phi(p^2) = p*( p-1)......(1)
          phi(p)=p-1..........(2)

          Using 1 and 2
          in
          phi( (p^2) ) = [phi(p)]^2 + phi(p)
          we get
          p*(p-1) = (p-1)^2 + p-1

          I think the result is obvious.........for the if
          case.

          Now for the only if case

          Let N = p(1)^a(1) * p(2)^a92)*........*p(n)^a(n)

          phi(N) =
          p(1)^{a(1)-1}*p(2)^{a(2)-1}*......p(n)^{a(n)-1}*{p(1)-1}*{p(2)-1}.....{p(n)-1}

          N^2= p(1)^2a(1) * p(2)^2a(2)*........*p(n)^2a(n)

          phi(N^2) =
          p(1)^{2a(1)-1}*p(2)^{2a(2)-1}*......p(n)^{2a(n)-1}*{p(1)-1}*{p(2)-1}.....{p(n)-1}

          Now if the equation holds then

          phi( (p^2) ) = [phi(p)]^2 + phi(p)

          phi(N^2) = phi(N)^2 + phi(N)
          ==>
          [p(1)^{2a(1)-1}*p(2)^{2a(2)-1}*......p(n)^{2a(n)-1}*{p(1)-1}*{p(2)-1}.....{p(n)-1}]
          =
          [p(1)^{a(1)-1}*p(2)^{a(2)-1}*......p(n)^{a(n)-1}*{p(1)-1}*{p(2)-1}.....{p(n)-1}]^2
          +
          [p(1)^{a(1)-1}*p(2)^{a(2)-1}*......p(n)^{a(n)-1}*{p(1)-1}*{p(2)-1}.....{p(n)-1}]

          Cancelling off the common terms from both the sides
          (implies none of p(i) = 1 or 0 )

          The equation yields

          p(1)^a(1) * p(2)^a92)*........*p(n)^a(n)=
          p(1)^{a(1)-1}*p(2)^{a(2)-1}*......p(n)^{a(n)-1}*{p(1)-1}*{p(2)-1}.....{p(n)-1}
          + 1

          N = phi(N) + 1

          Or phi(N) = N-1
          which is true iff N = prime


          I think the proof is over
          and the statement is very correct.

          Shiv Nandan Singh





          Shiv Nandan Singh

          --- William Bouris <melangebillyb@...> wrote:
          > Hello Group...
          >
          > Can someone prove or disprove?
          >
          > phi( (p^2) ) = [phi(p)]^2 + phi(p) iff "p" is prime,
          > and phi(...) is the totient function.
          >
          > Or is this equation already known? Bill.
          >
          >
          > -




          __________________________________
          Do you Yahoo!?
          Win a $20,000 Career Makeover at Yahoo! HotJobs
          http://hotjobs.sweepstakes.yahoo.com/careermakeover
        Your message has been successfully submitted and would be delivered to recipients shortly.