EULER(1)=1, not 0

Contrary to HP CAS, EULER(1)=1, not 0.
by Joseph K. Horn, 2 Nov 2005

Table of Contents:

0. Introduction
I. Scholarly Website References
II. Scholarly Literary References
III. Examples in Computer Science
IV. Pertinent Properties of EULER(n)

----------------

0. INTRODUCTION

There is a bug in the EULER function (more commonly known as the phi
function) in HP's CAS that would be trivial to fix but it remains
unfixed because the CAS programmers are erroneously convinced that
EULER(1)=0. EVERYBODY other than HP says that EULER(1)=1, and in fact
Number Theory itself requires it. Hopefully the following will
convince HP of this, and motivate them to debug the EULER function...
something that years of my personal carping have failed to do.

----------------

I. SCHOLARLY WEBSITE REFERENCES TO PHI(1)=1:

(1) Eric W. Weisstein. "Totient Function." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/TotientFunction.html

"The totient function EulerPhi[n], also called Euler's totient
function, is defined as the number of positive integers less than or
equal to n that are relatively prime to (i.e., do not contain any
factor in common with) n, where 1 is counted as being relatively prime
to all numbers."

"The first few values of EulerPhi[n] for n=1, 2, ... are 1, 1, 2, 2, 4,
2, 6, 4, 6, 4, 10, ... (Sloane's A000010)."

Wolfram also gives a table of phi(n) here:
http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/03/02/
in which phi(1)=1.

--------

(2) Neil Sloan's Online Encyclopedia of Integer Sequences:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000010
phi(1)=1.

--------

(3) Chris Caldwell, "Euler's phi function." From "The Prime Glossary"
http://primes.utm.edu/glossary/page.php?sort=EulersPhi

"Euler's phi (or totient) function of a positive integer n is the
number of integers in {1,2,3,...,n} which are relatively prime to n."

Table shows phi(1)=1.

--------

(4) Andreas de Vries, "The Euler Totient Function phi." From "m@th IT"
http://math-it.org/Mathematik/Zahlentheorie/Euler.html

Table shows phi(1)=1.

--------

(5) David Joyner, "Euler's phi function." From "Applied Abstract
Algebra"
http://web.usna.navy.mil/~wdj/book/node15.html

Table shows phi(1)=1.

------------------

II. SCHOLARLY LITERARY REFERENCES TO PHI(1)=1:

(1) Graham, Knuth, Patashnik, "Concrete Mathematics" (Addison-Wesley,
1994)

Pg 115: "When gcd(m,n)=1, the integers m and n have no prime factors in
common and we say that they're << relatively prime >>."

Pg 133: "How many of the integers {1, 2, ... m} are relatively prime to
m? This is an important quantity called phi(m), the << totient >> of m.
.... We have phi(1)=1, phi(prime)=prime-1, and phi(m)<m-1 for all
composite numbers m."

--------

(2) B.M. Stewart, "Theory of Numbers" (Macmillan, 1952)

Pg 103: "The Euler phi-function (sometimes called the totient function)
is a widely used number-theoretic function, almost always indicated by
phi(n). For n=1, we define phi(1)=1."

--------

(3) Emil Grosswald, "Topics from the Theory of Numbers" (Macmillan,
1966)

Pg 43: "The number of positive integers r, not exceeding m and coprime
with m is denoted by phi(m). ... Examples: phi(1)=1 ... This function
phi(m) is usually called Euler's phi-function."

--------

(4) William H. Beyer, Ph.D., "CRC Standard Mathematical Tables" (CRC
Press, 1981)

Pg 102: "phi(n) is the number of integers not exceeding and relatively
prime to n."

The subsequent table starts with phi(1)=1.

--------

(5) Oystein Ore, "Number Theory and its History" (McGraw-Hill, 1948)

Pgs 110 and 114: "phi(1)=1".

--------

(6) Albert H. Beiler, "Recreations in the Theory of Numbers" (Dover,
1966)

Pg 321: Table 102 shows phi(1)=1.

------------------

III. EXAMPLES OF PHI(1)=1 IN COMPUTER SCIENCE:

(1) UBASIC: EUL(1) --> 1
(2) Mathematica: EulerPhi[1] --> 1

------------------

IV. PROPERTIES OF PHI(N) THAT REQUIRE PHI(1) TO BE 1:

(1) Theorem: The sum over the Euler function values phi(d) of all
divisors d of an integer number n exactly gives n.

Example for n=12:
SUM(PHI(DIVISORS(12))) =
SUM(PHI{ 1 2 3 4 6 12 }) =
SUM{ 1 1 2 2 2 4 } =
12.

In hp49g+ RPL, z DIVIS EULER SigmaLIST (where z is a positive integer
object) should always return z, but instead it returns z-1, because it
thinks EULER(1)=0.

--------

(2) Theorem: Phi(x) is multiplicative. That is, if gcd(a,b)=1, then
phi(a*b)=phi(a)*phi(b).

Example: gcd(3,5)=1, so phi(3*5)=phi(3)*phi(5).

But gcd(1,2)=1. Therefore, phi(1*2) ought to equal phi(1)*phi(2), but
HP CAS says they are not equal; it gives EULER(1*2)=1, and
EULER(1)*EULER(2)=0.

-jkh-

.

Relevant Pages

  • Re: common factors of elements of a recursive sequence
    ... Given positive integers u0,u1,a,b. ... Take any urelatively prime to b, and let p be a prime dividing ... there is some k such that M^k = I (the identity matrix) mod p. ...
    (sci.math)
  • Re: "Less than less than" notation, <<
    ... constant depends on the subscripted quantity. ... Let A,B,C be relatively prime positive integers satisfying A+B=C. ...
    (sci.math)
  • Re: number problem ...
    ... Here's a sketch ... ... If x,y are distinct, relatively prime positive integers and ... Since x,y are relatively prime, so are y and. ... d divides p*y^p implies d divides p. ...
    (sci.math)
  • Re: Does x^2+y^2=z^50 have integer solutions?
    ... reference to which would answer the question completely. ... I'll take credit for most of the "false theorems" in this thread. ... which positive integers can be expressed as a sum of 2 squares doesn't ... be relatively prime, and one for the general case. ...
    (sci.math)