Talk:Euler's totient function/Archive 1

This is an archive of past discussions about Euler's totient function. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

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? — Preceding unsigned comment added by Evilbu (talk • contribs) 19:04, 4 February 2006 (UTC)

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)

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)

Applications

What about applications of Euler's totient function? (Especially in CS)--User:Vanished user 8ij3r8jwefi 17:07, 16 May 2006 (UTC)

Phi Function

Can someone find phi(2695), phi(4312), and phi(5390)? They might all be the same. — Preceding unsigned comment added by 71.235.83.132 (talk) 21:15, 16 May 2006 (UTC)

They are indeed - all equal to 1680. And the significance is ... ? — Preceding unsigned comment added by Madmath789 (talk • contribs) 13:14, 19 May 2006 (UTC)

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)

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 OEIS: A000010 was the first result. The top of the Belgian PDF says "

\phi (n)=card\{k\in \mathbb {N} /k<netpgcd(k,n)=1\}

," which also has me confused. P.S. The URL has now been blacklisted so anyone wondering what we're talking about will have to look in the history. Anton Mravcek 23:03, 25 August 2007 (UTC)

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)

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)

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)

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)

Article title

Why is this article entitled Euler's totient function instead of totient function or just totient? Are there other totient functions than the one Euler defined? I have never heard of any other totients running around, but then again perhaps some obscure-to-me mathematician in some prior century defined a different totient function. If other totient functions exist other than Euler's either this article needs to have a section called "Other uses of totient" or those other Joebob's totient function and Snicklefritz's totient function need to appear in the "See also" section of this article. I find it odd that this article is named with a surname and other mathematical articles lack a genitive surname reference to their discoverer/designer, except where the common name refers to the person such as the Pythagorean theorem. —optikos (talk) 03:59, 24 June 2008 (UTC)

Indeed. There is a Jordan totient function [1][2] see Camille Jordan, indeed PlanetMath has a general definition of a Totient of which Euler's is just one. We may need a Totient (disambiguation).

p.s. this question arose for me when trying to workout the correct DEFAULTSORT for Proofs involving the totient function should it be {{DEFAULTSORT:Totient function, Proofs involving the}} or {{DEFAULTSORT:Euler's Totient function, Proofs involving the}}--Salix (talk): 20:20, 26 September 2008 (UTC)

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)

Here's a much faster function using prime factorisation. (If n's distinct prime factors are a, b and c then the totient is n(1-1/a)(1-1/b)(1-1/c).) Produces the same results as above, but with only around sqrt(n)/3 divisions in the worst case.

   int totient(int n)
   {
       if (n <= 1) return n == 1 ? 1 : 0;
       int phi = n;
       if (n % 2 == 0) { phi /= 2;       n /= 2; while (n % 2 == 0) n /= 2; }
       if (n % 3 == 0) { phi -= phi / 3; n /= 3; while (n % 3 == 0) n /= 3; }
       for (int p = 5; p * p <= n; )
       {
           if (n % p == 0) { phi -= phi / p; n /= p; while (n % p == 0) n /= p; }
           p += 2;
           if (p * p > n) break;
           if (n % p == 0) { phi -= phi / p; n /= p; while (n % p == 0) n /= p; }
           p += 4;
       }
       if (n > 1) phi -= phi / n;
       return phi;
   }

Defenestrator (talk) 07:54, 13 July 2010 (UTC)

Euler product

"This last formula is an Euler product and is often written as"

Is this right? The previous formula is expressed in terms of k, the supposedly equivalent formula following hasn't a k in it anywhere. How can they be equivalent? --jdege (talk) 14:40, 15 August 2008 (UTC)

Changed the formula to (hopefully) clarify this. If it goes away, you basically just multiply top-and-bottom by n, which cancels all the $k_{i}$ parts and leaves a $1-1/p$ term for each $p$ . Traviscj (talk) 01:41, 9 September 2010 (UTC)

W. Schramm

In the Computing section, the following formula is used:

\varphi (n)=\sum \limits _{k=1}^{n}{\operatorname {gcd} (k,n)\cdot \exp \left({\frac {-2\pi ik}{n}}\right)}.

Can someone explain the derivation of this formula? I don't understand how this works, as you have an imaginary part on the right side of the equation but not on the left. —Preceding unsigned comment added by Devnullnor (talk • contribs) 12:03, 7 March 2010 (UTC)

BTW, this is not what Schramm has shown, the attribution is wrong. It's an expansion of phi and was shown by the man himself (Euler). Schramm showed expansions of gcd(k,n), which is a different problem. — Preceding unsigned comment added by 71.206.142.54 (talk) 09:28, 13 June 2011 (UTC)

phi(1000) on the plot

Euler's phi(1000) = 400 does not appear on the plot of the first 1000 values of phi. 72.83.89.94 (talk) 15:47, 25 June 2011 (UTC)

Yes, but I think that hardly makes any difference. If you'd like to correct it, register and you'll be able to upload a new version of the plot. Or tell the user who originally made the picture (it:User:Toobaz) about this mistake. -- X7q (talk) 20:39, 25 June 2011 (UTC)

Inequality

Can anyone show me how to prove

{\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)

for n>1? Thanks. Supermint (talk) 16:39, 27 March 2011 (UTC)

Hardy & Wright, Thm. 329. See http://en.wikipedia.org/wiki/Arithmetic_functions#Miscellaneous

Virginia-American (talk) 13:52, 7 December 2011 (UTC)

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)

Incorrect example or confusing definition

The first paragraph may be incorrect, for if you count the positive intergers less than or equal to 9 that don't have commmon factors with 9 besides 1, it will total 7, as it is in the example {1,2,4,5,7,8,9}. Only if it included the positive integers less than 9, it would be 6. —Preceding unsigned comment added by Flaviano Horozimbo Pires (talk • contribs) 18:13, 26 March 2010 (UTC)

You think 9 doesn't have any common factors with itself?? —David Eppstein (talk) 19:15, 26 March 2010 (UTC)

Thanks for taking that bullet Flaviano. I'm still confused, however. If k and n are relatively prime, then their greatest common divisor must be 1. But if this function "...counts the number of positive integers less than or equal to n...", then k could equal n. In that case, gcd(n, k) = n and n will often be something other than 1. Doesn't "or equal to" violate the restriction of being relatively prime? --Pbyhistorian (talk) 02:28, 9 August 2012 (UTC)

Nope. John Behind The Curve (talk) 02:33, 9 August 2012 (UTC)

In keeping with WP's spirit of elucidation, perhaps I can do a little better than that. Bo states above that n is not relatively prime with n, so the restriction "that are relatively prime to n" excludes n from the count when n > 1 and the addition of "or equal to" simply ensures that 1 is not excluded from the count by "less than...n" when n = 1 (per Woodstone above). --Pbyhistorian (talk) 19:40, 9 August 2012 (UTC)

Lower limit explained

I would like to know more about the lower limit of the co-primes. In the pictures it is shown as 4x/15, but there is no reference to this within the article. I am assuming that there is a reason for this based on the limit of some algorithm within this article. I assume there is such a proof or else, this function would not be labelled within the image. If anyone can explain this I would like to see it posted within the article. — Preceding unsigned comment added by Peawormsworth (talk • contribs) 08:51, 1 September 2012 (UTC)

I found an answer to my own question: "Note that the lower bound of y = 4n/15 is not a real lower bound! It only occurs where n is a multiple of 30. There are many values below that line. (So this is not a lower bound for the whole totient function, but only for these first few values of n.)". This is a note attached to the image. If this is true, then I would suggest we completely remove this slope equation (y = 4n/15) from the image. Because it gives the reader a false impression that this is a true bound of the function. But it is not. If no one complains about this suggestion... I will go ahead and remove it from the image within the near future. — Preceding unsigned comment added by Peawormsworth (talk • contribs) 09:01, 1 September 2012 (UTC)

On the topic of lower limits, saying there is no linear lower bound is false, y = 0 is never reached. That section needs clarification, unless I am misunderstanding somthing.134.129.203.28 (talk) 21:13, 24 April 2013 (UTC)

Of further note, the article on bounds says:

Every subset of the natural numbers has a lower bound, since the natural numbers have a least element (0, or 1 depending on the exact definition of natural numbers). An infinite subset of the natural numbers cannot be bounded from above. An infinite subset of the integers may be bounded from below or bounded from above, but not both. An infinite subset of the rational numbers may or may not be bounded from below and may or may not be bounded from above.

Which indicates I'm correct, but I'm uncomfortable changing this until someone who has already worked on the article verifies.134.129.203.28 (talk) —Preceding undated comment added 21:24, 24 April 2013 (UTC)

Sorry, no. The "linear lower bound" would be 0; there is no number

ε > 0

such that

φ(n) > ε n

for all

n > 1

. — Arthur Rubin (talk) 22:29, 24 April 2013 (UTC)

There used to be a very nice set of bullet points about lower bounds in this article which I thought were quite helpful. Certainly it's necessary to give the "truthful" lower bound n/(loglogn + c) but it was really nice to have more practical bounds such as sqrt(n) < phi(n) for n>6 or n^(1/3) <phi(n) for n>2. Especially if coding something, it's easiest to start from a list which goes up to N^2 or N^3 before you get started with the actual work. Is there any particular reason these were removed?129.133.93.86 (talk) 15:16, 3 June 2013 (UTC)

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:

\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 (ϕ) is more frequent than the handwritten one, which in turn is preferred for angles (I think).— MFH:Talk 13:16, 3 June 2008 (UTC)

An italic html phi looks more like the tex angled one: φ. —David Eppstein (talk) 15:14, 16 June 2013 (UTC)

Untitled

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 (talk) 08:15, 23 June 2005 (UTC)

Totient rhymes with division's quotient. —optikos (talk) 03:48, 24 June 2008 (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 June 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 (talk) 17:24, 23 June 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 June 2005 (UTC)

Noted. —Tokek (talk) 19:06, 23 June 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)

Notation - needs editing

In the section titled History, Terminology and notation, the notation is NOT explained. That is really really lame. A link is provided to Arithmetic Functions where the notation is only partially explained. This link is not in the notation section!! More massive lameness. If you are going to write it, explain it. Gamma d|n and Sigma d|n are explained, but a|b is NOT explained nor is phi(n)|phi(m). In the linked article the explanation of the notation linked to is just two lines. WTF wasn't it included here?? I would cut and paste it, but since I haven't the faintest idea what a|b means, perhaps one of the illuminati can condescend? $\sum _{d|n}f(d)\;$ and $\prod _{d|n}f(d)\;$ mean that the sum or product is over all positive divisors of n, including 1 and n. E.g., if n = 12,

\prod _{d|12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).\

p|n also needs explanation as an index = all prime divisors of n. And possibly the Fourier Transform notation... Thanks?72.172.11.228 (talk) 17:20, 28 May 2013 (UTC)

In addition, if the notation is as described on the Arithmetic Functions page as shown in the product above (i.e. it includes 1 and n) then shouldn't it follow that:

\prod _{p|n}(1-{\frac {1}{p}})=(1-{\frac {1}{1}})\times \cdots \times (1-{\frac {1}{n}})=0.\

That is pretty clearly incorrect, but it is what a literal reading of the notation description would lead one to believe.— Preceding unsigned comment added by 128.138.65.99 (talk • contribs) 15:10, 30 May 2014‎

The article says "where the product is over the distinct prime numbers dividing n". As 1 is not a prime number,

(1-{\frac {1}{1}})

cannot appear in the product, and the product is never zero. Similarly, the factor

(1-{\frac {1}{n}})

, may appear only if n is prime. In this case, it is the only factor.

D.Lazard (talk) 15:56, 30 May 2014 (UTC)

Calligraphic O

I suppressed the calligraphic O for the Landau symbol. This font is simply never used in number theory in the literature (in computer science I don't know). I've seen it only in some wikipedia pages… Sapphorain (talk) 22:36, 7 July 2014 (UTC)

I've seen it used in computer science but it's not universal there. Anyway this article is number theory not CS. So I agree with this decision. —David Eppstein (talk) 23:29, 7 July 2014 (UTC)

Definition of φ(0)

The edit summary for this reversion says: "The function is not defined for n=0." That statement should be in the article and sourced. See Hardy & Wright: 5.5 Euler's function φ(m).

The edit summary for this subsequent reversion says: "Mathematica defines EularPhi(0) as 0". That statement should also be in the article and an explanation given. See the Mathematica documentation for EulerPhi and this sentence from MathWorld:

"By convention, phi(0)=1, although Mathematica defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command."

(Weisstein, Eric W. "Totient Function". MathWorld.)

--50.53.60.172 (talk) 07:51, 24 October 2014 (UTC)

I find the assertion "By convention, phi(0)=1" very suspect; I am a number theorist and I have never heard of such a convention before. In general I think the informations from "Mathworld" should be taken with care, especially those pertaining to definitions and history, and verified elsewhere before they are included in Wikipedia: "Mathworld" is also an online encyclopedia, but with essentially one single contributor, who is not originally a mathematician (nor a historian).

Regarding the fact that Mathematica provides the value 0 for phi(0) (or any value): it appears to me as a bug, that should be removed as soon as possible. Sapphorain (talk) 08:45, 24 October 2014 (UTC)

I agree with Sapphorain. Moreover, giving a value for phi(0) in the table would implies changing accordingly the first paragraph of the lead and making it unsourced, as the sources 1 and 2 define the totient function only for positive integers. As these sources are highly reliable on this subject, much more than Mathworld and Matematica, such a change would break two Wikipedia policies: WP:Verifiability and WP:Neutral point of view. — D.Lazard (talk) 12:28, 24 October 2014 (UTC)

The article should explicitly state that φ(0) is undefined by Hardy & Wright and any other number theory sources you care to cite. The table should conform to that.
A bug is a mistake. The Mathematica convention is not a bug. The Mathematica documentation for EulerPhi says EulerPhi[0] returns 0. (look under "Possible Issues"). The article should acknowledge that fact — this is an encyclopedia, not a number theory textbook.
The MathWorld statement that "By convention, phi(0)=1" is not explicitly sourced, despite a huge reference section, so MathWorld is unreliable on that point.

--50.53.60.172 (talk) 13:20, 24 October 2014 (UTC)

Clarification: Hardy & Wright do not explicitly state that φ(0) is undefined. In their definition of φ(

m

), the domain of φ is implied by their inequality:

$0<n\leq m$ (§ 5.5, p. 52)

--50.53.60.172 (talk) 13:58, 24 October 2014 (UTC)

Here is a simple solution for the table: Add a note above the table that explicitly states that φ(0) is undefined by various cited sources. --50.53.60.172 (talk) 14:18, 24 October 2014 (UTC)

The issue here is not how phi(0) should be defined, but whether is should be defined at all. For a number of very good reasons, related to the underlying structures of the sets of arithmetical functions and of the multiplicative arithmetical functions, to which the phi function belongs, it should definitely not be defined. Indeed these are groups under the Dirichlet convolution; but, as every positive integer is a divisor of 0, the Dirichlet convolution f*g(n) is undefined if n=0. Thus, for f an arithmetical function, f(0) is never defined in good textbooks, in which these underlying structures are studied: the set of arguments for f is the set of of positive integers. So there is no point in providing sources in which phi(0) is not defined: no serious source will define it.

Maybe the value for phi(0) provided by Mathematica is not, strictly speaking, a bug, as it appears to be intentional. But being intentional doesn't change the fact that it is a mistake. Besides, we don't even know who decided to provide this strange output, and why. Sapphorain (talk) 16:40, 24 October 2014 (UTC)

"The issue here is not how phi(0) should be defined, but whether is should be defined at all."

You are wasting your time explaining why or why not φ(0) should be defined. WP requires verifiable and reliable sources, so it would be more constructive if you provided some sources making your point.

And the article is biased, because it does not say what a highly-respectable software product does. The MathWorld article offers an explanation for why EulerPhi[0] returns 0:

"... Mathematica defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command." (link)

Do you know what that means?

For your convenience, here are links to the Mathematica documentation for EulerPhi and FactorInteger.

--50.53.60.172 (talk) 17:39, 24 October 2014 (UTC)

Yes, indeed, I think I have been wasting my time. Sapphorain (talk) 21:07, 24 October 2014 (UTC)

'..."Mathematica defines EularPhi(0) as 0". That statement should also be in the article and an explanation given.'

EulerPhi also accepts negative integers. For example, WolframAlpha shows that EulerPhi[-60] is 16.

--50.53.60.172 (talk) 03:20, 25 October 2014 (UTC)

This is becoming quite ridiculous. How about complex values of the argument? If you wish to mention an extension of the Euler function defined only by "a highly respectable software product" and considered nowhere else, I think you'll have to do it in a footnote. Sapphorain (talk) 08:01, 25 October 2014 (UTC)

(edit conflict) This simply confirm that Mathematica is not a reliable source. No need of wasting our time for that. D.Lazard (talk) 08:07, 25 October 2014 (UTC)

Sapphorain: "... an extension of the Euler function ..."

That's an excellent way to describe the domain of the software function EulerPhi. Haven't any mathematicians discussed the domain of the mathematical function φ? A footnote about EulerPhi would be fine, if the article clearly stated that mathematicians do not define

φ(n)

for

n < 1

and explained why. (It has something to do with the solution to the equation

gcd (n, k) = 1

for

n < 1

.)

D.Lazard: "... Mathematica is not a reliable source."

The Mathematica documentation is a reliable source for what the software function EulerPhi does. Indeed, the documentation says:

" $φ(- n)$ is taken to be equal to $φ(n)$ ."

--50.53.35.240 (talk) 13:37, 25 October 2014 (UTC)

No. It's the modification that must be explained, not the other way around. Provided a footnote on this matter is justified, it should clearly state that Mathematica very recently (when?) decided to extend to n<1 the phi function, introduced by Euler in 1763, and explain why. Sapphorain (talk) 15:24, 25 October 2014 (UTC)

By WP:NPOV, if we describe the specificities of Mathematica implementation of the function, we must do the same for the other software that implement it, which include at least Maple, Magma, GP/PARI, GAP, and certainly also Macsyma, Maxima, Sage. For the record, in Maple, the function is called Numtheory[phi]. A section about the various implementations could be written, but not really useful, as the implementation of this function is an easy exercise for a beginner in computer algebra. Moreover such a section could be based only on primary sources, and therefore would be original synthesis. D.Lazard (talk) 16:44, 25 October 2014 (UTC)

The Maple documentation for numtheory[phi] says that it accepts an integer as a parameter, but it doesn't say what the function returns for

n < 1

. You have a point re WP:NPOV, but neither of you have yet provided a sourced explanation for why

φ(n)

is not defined for

n < 1

. BTW, Euler wrote in Latin (link from the article). --50.53.34.31 (talk) 05:31, 26 October 2014 (UTC)

Sage: "Notice that euler_phi is defined to be 0 on negative numbers and 0." --50.53.34.31 (talk) 06:27, 26 October 2014 (UTC)

The MuPAD function numlib::phi(n) accepts an argument that is an "Integer not equal to zero". Example 1 shows that numlib::phi(-7) returns 6. --50.53.40.60 (talk) 11:53, 26 October 2014 (UTC)

The documentation for the Maxima function "totient" does not say what it returns for 0 or negative integers, but I installed it and found that it does what Mathematica does:

(%i2) totient(16);
(%o2)                                  8
(%i3) totient(-16);
(%o3)                                  8
(%i4) totient(0);
(%o4)                                  0

--50.53.40.60 (talk) 16:08, 26 October 2014 (UTC)

The Maxima source code can be downloaded here. The "totient" function is implemented in maxima-5.34.1/src/numth.lisp. Unfortunately, there are no explanatory comments, but the implementation is definitely not a bug. In particular, the function takes the absolute value of its argument: (setq n (abs n)). --50.53.40.60 (talk) 16:53, 26 October 2014 (UTC)

"[Maxima] does what Mathematica does"

Mathematica and Maxima also agree that gcd(0,0) is 0. (link to WolframAlpha)

--50.53.60.41 (talk) 09:34, 27 October 2014 (UTC)

"Euler wrote in Latin": wow! what a scoop! So you've been insisting on changing things on this article without knowing the first thing on Euler, and clearly very little on the phi function itself. I am not going to discuss this matter any further with you and your numerous ip avatars. The only sensible thing you wrote here is that I am wasting my time: I will not waste it any more. Sapphorain (talk) 11:04, 26 October 2014 (UTC)

Alternate way to find Euler's Totient Function of Odd Composite

Let 'N' be any odd composite.

Find semi-prime Sp = uv such that

(2u+1)(2v+1) <= N <= 3(2Sp+1). or N <= (2u+1)(2v+1) < 3(2Sp+1)

For example: let N = 65 then required semi-prime is 14 = 2*7 such that 65 < (2*2 + 1)(2*7 +1) < 3*(2*14 + 1) i.e., 65 < 5*15 < 3*29 i.e., 65 < 75 < 87

Note: Finding Semi-prime Sp will be optimized through Trial & Error

Let Lsp be any semiprime nearer and lesser than Sp compared to other.

Then Euler's Totient function Phi(N) = 4*(Sp - k) where 0 <= k <= (Sp - Lsp).

For example: for 65 = 5*13 Phi(65) = 4*12 = 48 = 4*(14-2) Look above example Sp = 14, Lsp = 9, Sp - Lsp = 14-9 = 5; here we saw that 0 < k < 5 — Preceding unsigned comment added by Yourskadhir (talk • contribs) 06:29, 5 March 2015 (UTC)

Even if this were accurate and sourced, it still wouldn't seem helpful. — Arthur Rubin (talk) 01:56, 11 March 2015 (UTC)

The name of the function

I am an American number theorist, and I cannot find a single book in my shelves that calls the Euler phi function the "totient" or "Euler totient" function. It is in all cases referred to as the Euler phi function. I think for a function as well-used as this one, especially by undergraduates, we should use standard terminology. It is hard to cite all the references -- please look at any number theory book on your shelf. I am curious about what other readers think.Jaatex (talk) 19:19, 11 April 2015 (UTC)

I am an American number theorist, and in no reference on my shelf is the Euler phi function called the totient function or the Euler totient function. With a function as well-used as this, especially by undergraduates, shouldn't we use the standard name? I'm curious how others feel. Jaatex (talk) 19:27, 11 April 2015 (UTC)

I am also a number theorist, and have very often heard the phi function called the "totient function", or "Euler totient function". The term was apparently invented by Sylvester. It is mentioned by Niven and Zuckerman (3rd edition, p.22). In the "Handbook of estimates in the theory of numbers" (B. Spearman, K.S. Williams, Carleton Mathematical Lecture Note 14, 1975), on the definition p. 4, phi is called "Euler's totient function". If you search on MathSciNet, you will find that the number of articles containing in their titles "Euler totient function" is 34 (73 for "Euler phi function"), and that the number of referee's reports citing "Euler totient function" is 386 (225 for "Euler phi function"). (Searching for just "totient function" is misleading: there are many other totient functions). Sapphorain (talk) 20:57, 11 April 2015 (UTC)

Thanks for the research. As you found, two-to-one in titles it is referred to as the Euler phi function. My bookshelf research: Ireland and Rosen, "A Classical Introduction to Modern Number Theory" and Pierre Samuel (translated from French), "Algebraic Theory of Numbers"; Kenneth H. Rosen "Elementary Number Theory"; Joseph H. Silverman, "Number Theory"; David M. Burton, "Elementary Number Theory" (the only reference where "totient" is mentioned: "The function \phi is usually called the \it {Euler phi-function} (sometimes, the \it indicator or \it totient)"); Serge Lang, "Algebra"; and "Andre Weil, "Number Theory, An approach through history...". In the above references, totient is neither in the index nor the text (except as noted in Burton, where it is not in the index). I understand that totient function terminology is sometimes used, and that it is historical. My point is that it is not commonly used. If a student tries to look up the totient function in a standard text, they will find nothing. I'm not sure why totient was chosen for the title of this article. I would like to change it to the more common name. Jaatex (talk) 14:39, 15 April 2015 (UTC)

In the past, this page was named "Euler's phi function". It is not clear when the name has changed, but the first line has been changed in 2003, apparently without any discussion, by this edit [3]. In any case, as both Phi function and Euler's phi function redirect to this article, the reader searching for this article will find it easily. Personally, I have no opinion on the best title nor for the name that should be used in the article (as far as both names appear in the first sentence). D.Lazard (talk) 15:23, 15 April 2015 (UTC)

Thank you for this information. This is my first attempt to edit a Wikipedia page. I see the edit from 2003, thanks for pointing it out. I do not see why the change was made. How was the change made without discussion? How does one go about getting it changed back? Do people vote? :-) Jaatex (talk) 15:54, 15 April 2015 (UTC)

In Wikipedia, decisions are taken by consensus, as described in details in WP:CON. However, few people have given their opinion. One could start a WP:request for comments. But, as nobody disagrees formally with you, and your arguments are convincing, I have self-reverted my revert of your edits. The change of title (called move in WP) seems less important than editing the content, because the title you suggest exists as a WP:redirect. For technical reasons, it may be done (in this case) only through a WP:move request. D.Lazard (talk) 19:12, 15 April 2015 (UTC)

Totient numbers

This section contains there are infinitely many nontotients, and indeed every odd number has an even multiple which is a nontotient, the word "even" being added by a recent edit. In both versions, this sentence is a nonsense, as every odd number greater than 1 is a nontotient; thus no need to consider multiples. I guess that the correct assertion should be every totient has a multiple (by an odd number) that is a nontotient. However this needs to be checked on the source. D.Lazard (talk) 09:59, 25 April 2015 (UTC)

As you say, odd numbers greater than 1 are trivially nontotients, so what is of interest is the existence of even nontotients. I imagine the previous writer meant "there are infinitely many even nontotients, and indeed..." but just forgot the "even". I've checked the paper and in fact it proves that any number (even or odd) has a multiple which is a nontotient. If n is odd then the nontotient multiple of 2n gives an even nontotient multiple of n, so this is equivalent to saying any number has an even nontotient multiple. I'll make those changes. Especially Lime (talk) 08:54, 20 May 2016 (UTC)

Unexplained revert of style improvement

My edit in Euler's totient function#Euler's product formula has been reverted by an IP user, without any explanation. My edit consisted in

Removing, per MOS:HEADINGS the redundant reference (through a formula) to the article title.
Replacing a heading consisting of a technical formula by a less technical phrase (the formula was redundant, as reproduced in the body
Avoiding the confusing term "modulo-and-coprime", which is nowhere defined in Wikipedia
Linking coprime

All are style improvements that does affect in any way the content of the article. As I cannot find any valid reason for rejecting these edits, I have restored them. Please, if I have missed something, please discuss here before a second revert. D.Lazard (talk) 15:52, 13 January 2017 (UTC)