Fw: Euler's Phi Function

[Adrian Daigle]

Not sure what this has to do with cryptography, but ...

You really want phi(1) = 1. Whether you do it by using your second
definition

	phi(n) = #{ 1 <= x <= n : gcd(x, n) = 1 }

or by using your first

	phi(n) = #{ 1 <= x < n : gcd(x, n) = 1 }

and just defining phi(1) = 1 by fiat is up to you.

If you have phi(1) = 1, then phi becomes a multiplicative function:

	phi(a) * phi (b) = phi(a * b) for all a,b with gcd(a,b) = 1.

And as every number theory guy knows, multiplicative functions are fun and
useful and all that stuff.


Adrian


On Mon, 24 Feb 2003, Damien O'Rourke wrote:

> I'm just after thinking about 1.  1 is relatively prime to itself but it
> would be the only positive integer.
> However if we take the first definition as correct then phi(1) might be
> considered meaningless as
> there are no positive integers less than 0.  I suppose however, that this
> could mean that
> phi is equal to 0 in this case but it doesn't it equals 1.  This is
> rectified in the second definition
> because it is less than or equal to itself and also relatively prime to
> itself which gives a value of 1
> for phi(1) as expected.
>
> Any thoughts would be great.
>
> Regards,
> Damien.
>
>
> ----- Original Message -----
> From: "Damien O'Rourke" <orourked at eeng.dcu.ie>
> To: <cryptography at wasabisystems.com>
> Sent: Monday, February 24, 2003 12:54 PM
> Subject: Euler's Phi Function
>
>
> > Hi,
> >
> > I have seen two slightly different definitions for the Euler's phi
> function.
> > They don't cause any difference in its value
> > but I was just wondering if there would be anyone who would complain about
> > the use of one or the other?
> >
> > One says that for a positive integer n, phi(n) is the number of positive
> > integers less than n and relatively prime to it.
> > The other differs slightly by saying that it's the number of positive
> > integers less than or equal to n and relatively prime
> > to it.  Because n is not relatively prime to itself this doesn't make a
> > difference in its value and using "less than or equals" seems slightly
> > superfluous, however, I am writing a report and I just want to be very
> > precise about the whole thing.  Thanks for your help.
> >
> > Regards,
> > Damien.
> >
>
>
> ---------------------------------------------------------------------
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com
>

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com