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

phi of n factorial proof

Expand Messages
  • Sebastian Martin
    Hello All: I send you a proof by Carlos Rivera of my Result Phi(n!)=Product(Ci)*Product(pi-1): The Euler Totient Function applied to factorial. (22 Feb. 2006)
    Message 1 of 1 , Feb 27, 2006
    • 0 Attachment
      Hello All:

      I send you a proof by Carlos Rivera of my Result

      Phi(n!)=Product(Ci)*Product(pi-1):



      The Euler Totient Function applied to factorial.

      (22 Feb. 2006)

      I.-Theorem: Phi(n!)= P(Ci). P(pi-1)

      Phi = Totient function
      n! = n.(n-1).(n-2). … 3.2.1
      P(Ci)=C1.C2. …
      Ci = composite, Ci<=n
      pi = prime, pi<=n

      II.- Example: Phi(10!) = Phi(3628800) =
      10.9.8.(7-1).6.(5-1).4.(3-1).(2-1).1 = 829440

      III.- Proof:

      n! =P(Ci).P(pj).P(pk)
      pj = prime <= n such that gcd(P(Ci), pj)<>1
      pk = prime <= n such that gcd(P(Ci), pk)=1

      then gcd(P(Ci).P(pj), P(pk))=1

      Phi(n!) = Phi(P(Ci).P(pj).P(pk)) =
      Phi(P(Ci).P(pj)).Phi(P(pk))

      Phi(P(pk)) = P(pk-1)

      But P(Ci)=P(pj^aj) where aj = # times pj occurs in
      P(Ci), then

      P(Ci).P(pj) = P(pj^(aj+1))

      Using Phi(p^b) = p^b(1-1/p) = p^(b-1).(p-1)

      We obtain Phi(P(Ci).P(pj)) = Phi(P(pj^(aj+1))) =
      P((pj^aj)(pj-1)) =
      = P(pj^aj). P(pj-1) = P(Ci). P(pj-1)

      Phi(n!) = P(Ci).P(pj-1). P(pk-1) = P(Ci).P(pi-1). End
      of proof.

      Corollaries:

      1) Phi(n!)/Phi((n-1)!)={n, if n=composite; n-1 if
      n=prime}

      2) (n-1)! <=Phi(n!) <= n!


      Sebastian Martin Ruiz Carlos Rivera

      http://perso.wanadoo.es/smaranda/
      http://www.primepuzzles.net/




      ______________________________________________
      LLama Gratis a cualquier PC del Mundo.
      Llamadas a fijos y móviles desde 1 céntimo por minuto.
      http://es.voice.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.