Talk:Euler's totient function

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class High Priority  Field: Number theory

The use of eight (8) for n (the argument to the totient function) in the opening paragraph might be misleading to some. All of it's coprimes are also prime. The use of nine (9) as the argument might be less misleading since it includes two composite numbers in it's set of coprimes. The number nine is also a power of a prime (just like eight) and thus allows simple computation of the totient. -Waylonflinn 22:38, 28 December 2006 (UTC)

How to pronounce totient?—Tokek 08:15, 23 Jun 2005 (UTC)

I think it is "toe shent". BTW, I prefer "the cototient is defined as" because it is a definition, not something that happens to be true. Bubba73 15:22, 23 Jun 2005 (UTC)

Both "is defined as" and "is" are appropriate, however you actually typed "defined as is" instead of "is defined as" so it required fixing. The statement can be taken as a definition for cototient either way.—Tokek 17:24, 23 Jun 2005 (UTC)
That was a typo. "is defined as" makes it clear that it is a definition. If they're both appropriate, why not use the one that is more appropriate (is defined as)? I wrote that line originally without the "defined" part. Then I realized that it would improve the article to have "defined" in there, so I changed it, but I accidently stuck it in at the wrong place. Bubba73 18:01, 23 Jun 2005 (UTC)
Noted. —Tokek 19:06, 23 Jun 2005 (UTC)

Doesn't totient(n) always equal a positive integer? Railgun 16:59, 26 June 2006 (UTC)

What does the phrase "randomly large n" mean? Should that be "general n"? 62.8.160.190 05:17, 26 July 2006 (UTC)

Contents

[edit] less or equal

In the definition

The totient φ(n) of a positive integer n is defined to be the number of positive integers less than n and coprime to n.

Ncik changed less that into less or equal than

As n is not coprime to n, I fail to see the improvement of this change. Ncik, please explain. Bo Jacoby 14:52, 2 December 2005 (UTC)

It makes a difference for n=1. The original definition would make the value 0, the correction makes it 1. −Woodstone 21:09, 2 December 2005 (UTC)

Is 1 really coprime to 1 ? Yes, according to definition. Thank you. Bo Jacoby 12:41, 8 December 2005 (UTC)

[edit] lim sup

there are better ways than mine to write lim sup and lim inf with bars over and under the lim respectively

can anyone do that? (User:Evilbu 4 Feb 2006)

Don't know; however, I think "lim sup" is clearer and more commonly used than symbols with lines over them. Notation should allways be clear in WP, since there are many readers from diverse backgrounds. linas 04:56, 5 February 2006 (UTC)

[edit] other relations

a useful relation is that phi(n) + sigma(n) = n * tau(n) for n prime

I also believe the distance from a highly composite number to the nearest prime (or in effect the largest prime factor of the HCN) is expressible in terms of phi and tau. A crude first stab at it is factor = ln[100 * (phi * * K1) / [tau * * (1 + K1)]]2,K1 = 0.55 Applies when the prime is not immed adjacent, thru 146th HCN --Billymac00 19:54, 15 May 2006 (UTC)

[edit] Applications

What about applications of Euler's totient function? (Especially in CS)--Čikić Dragan 17:07, 16 May 2006 (UTC)

[edit] Phi Function

Can someone find phi(2695), phi(4312), and phi(5390)? They might all be the same.

They are indeed - all equal to 1680. And the significance is ... ?

[edit] Different phis

Okay, what's up with the inconsistent usage of phi? The TeX version gives \phi\,, while the HTML version gives φ. Should this article use the same phi style, or does it really matter? -Matt 17:23, 3 September 2006 (UTC)

The TeX version is an uppercase phi, Φ. The lowercase phi can also be generated, \varphi \varphi. There are HTML-versions for both uppercase and lowercase phis too, Φ Φ and φ φ. I don't know for sure but I think the uppercase phi is the "official" symbol used to denote the Euler's totient function and thus that should be used. Currently all articles I have seen referring to this article unfortunately use the lowercase phi. But of course it would be simple to convert them into uppercase phis if so is agreed. --ZeroOne (talk | @) 17:33, 2 November 2006 (UTC)
The TeX \phi is not an uppercase phi; \Phi is. Both \phi and \varphi denote a lowercase phi, just differently styled. Fredrik Johansson 17:40, 2 November 2006 (UTC)
Confusing. Uppercase TeX phi: Φ. So you are saying that Euler's totient function should be denoted with a lowercase phi, then? --ZeroOne (talk | @) 18:37, 2 November 2006 (UTC)
Correct. Fredrik Johansson 18:47, 2 November 2006 (UTC)
No doubt: lowercase \phi. But indeed, especially on computers, I think the "straight" version (o+|) is more frequent than the handwritten one, which in turn is preferred for angles (I think).— MFH:Talk 13:16, 3 June 2008 (UTC)

[edit] value in 0

Are there references for discussions about phi(0)? I think it should not be defined, and I'm glad to see it is omitted from the table of values; in some computer algebra systems it gives an error ("*** eulerphi: zero argument in an arithmetic function." in PARI), but in others (Mathematica) it is defined to be 0. Obviously, it depends on which of the following definitions is used:

  • phi(n) = # U(Z/nZ)
  • phi(n) = # { k in N* | k <= n, gcd(k,n)=1 }

If the second is adapted, then phi(n)=0 for all n<1, while Mathematica inconsistently uses phi(-n)=phi(n), which only applies to the former definition (which in turn would give phi(0) = 2 = # {-1,1}).— MFH:Talk 13:16, 3 June 2008 (UTC)

[edit] To do

Article needs to say something about iterated totient function. Mentioned in article on perfect totient number. PrimeFan 00:35, 13 January 2007 (UTC)

[edit] less or equal

According to the logs, on 31 Jan 2007, Nberger changed "less than or equal" in the definition back to "less than". This subject came up in December 2005. I believe that "less than or equal" is correct. It makes a difference only for the value at 1, which should be 1 (as it is with "less than or equal") and not 0 (as it is with "less than").

P. N. Hilfinger 02:53, 22 February 2007 (UTC)

agree, "less than" is just incorrect. Farannan (talk) 02:53, 19 November 2007 (UTC)

[edit] Discrepancy in values

The first external reference leads to a Belgian website, which has a PDF file containing "1 000 premières valeurs de l'indicatrice d'Euler en pdf". I don't know for sure if this is intended to be the same function as the one described in this article, but for phi(36) it has 24, whereas in the article phi(36) is stated to be 12. If I've misunderstood, it's possible others will too. Also the other links on the Belgian webpage purport to be zip files of 100,1000,10000 values, but actually all point to the 100 values zip file. Windymilla 10:27, 25 August 2007 (UTC)

I'm confused about it, too. I tried putting in the first ten values into the OEIS and that gave me no results. I then tried the first ten values given here and A000010 was the first result. The top of the Belgian PDF says "\phi(n) = card \{k \in \mathbb{N}/k < n et pgcd(k, n) = 1\}," which also has me confused. Anton Mravcek 23:03, 25 August 2007 (UTC) P.S. The URL has now been blacklisted so anyone wondering what we're talking about will have to look in the history.

[edit] Scriptstyle?

For some reason the phi symbol was written as \scriptstyle\varphi, instead of \varphi, and was illegibly small. Script style is intended for sub/super-script size characters -- any idea why it was used? (Was there some formatting discussion that I missed?) I've reverted it. Nbarth 22:13, 18 October 2007 (UTC)

[edit] Clarity in derivation

I'm having trouble understanding this derivation:

\zeta(s) \sum_{n=1}^\infty \frac{\varphi(n)}{n^s} = \sum_{n=1}^\infty \left(\sum_{d|n} \varphi(d)\right) \frac{1}{n^s} = \sum_{n=1}^\infty \frac{n}{n^s} = \zeta(s-1),

Can someone explain in more detail what substitutions are happening? --CmaccompH89 (talk) 21:48, 7 December 2007 (UTC)

Sure. I recently had this problem myself. It's a very poorly explained derivation. Here's how it ought to go

\zeta(s) \sum_{f=1}^\infty \frac{\varphi(f)}{f^s} = \sum_{g=1}^\infty \frac{1}{g^s} * \sum_{f=1}^\infty \frac{\varphi(f)}{f^s}

\sum_{g=1}^\infty \frac{1}{g^s} * \sum_{f=1}^\infty \frac{\varphi(f)}{f^s} = \sum_{h=1}^\infty \left(\sum_{f*g=h} 1*\varphi(g)\right) \frac{1}{h^s}

\sum_{h=1}^\infty \left(\sum_{f*g=h} 1*\varphi(g)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \left(\sum_{d|h} 1*\varphi(d)\right) \frac{1}{h^s}

\sum_{h=1}^\infty \left(\sum_{d|h} 1*\varphi(d)\right) \frac{1}{h^s} = \sum_{h=1}^\infty \frac{h}{h^s}

\sum_{h=1}^\infty \frac{h}{h^s} = \zeta(s-1)

McDutchy (talk) 00:07, 8 December 2007 (UTC)

Thanks!, that makes much more sense, I'll insert it into the article. --CmaccompH89 (talk) 00:16, 8 December 2007 (UTC)

I would appreciate someone more knowledgeable with LaTeX than I am cleaning it up a bit. It's a little sloppy. McDutchy (talk) 01:08, 8 December 2007 (UTC)

[edit] C++ Example

I doubt this is very optimized. Using the "gcd" function found here: http://en.wikipedia.org/wiki/Euclidean_algorithm#Using_recursion (converted to c++) And some of my own bad programming I made this:

   int gcd(int a, int b)
   {
       if (!b) return a;
       return gcd(b, a%b);     
   }
   
   int totient(int x)
   {
       int total=0;
       for(int i=0; i<x; i++)
       {
                total = (gcd(x,i) > 1) ? total : total+1;
       }
        return total;
   }

From what I've tested it works fine. (Sorry, I can't get the code boxes to work properly) —Preceding unsigned comment added by 85.211.66.110 (talk) 19:42, 28 January 2008 (UTC)

(Got them right for you) 77.193.184.147 (talk) 16:26, 10 February 2008 (UTC)