(Leonhard Euler was born on 15th April 1707 in Basel, Switzerland and
he died on 18th September 1783 in St Petersburg, Russia).
If N is a positive integer, then phi(N) is defined to be the number of
positive integers less than or equal to N and coprime (do not contain
any factor in common with) to N.
Example (1):
Prime factor of 8 is only 2 => 8 = 2^3
phi(8) = phi(2^3) = phi(2 * 2^2) = (2-1) * 2^2 = 1 * 4 = 4.
The numbers of integers less than 8 that coprime with 8 are 4, they are
1, 3, 5 and 7.
coprime to 8?
Same Factor
1
yes, always
2
no
2
3
yes
4
no
2
5
yes
6
no
2
7
yes
Example (2):
Prime factor of 10 are 2 and 5 => 10 = (2^1) * (5^1)
phi(10) = phi(2) * phi(5) = (2-1) * (5-1) = 1 * 4 = 4.
The numbers of integers less than 10 that coprime with 10 are 4, they
are 1, 3, 7 and 9.
coprime to 10?
Same Factor
1
yes, always
2
no
2
3
yes
4
no
2
5
no
5
6
no
2
7
yes
8
no
2
9
yes
To calculate Euler totient function, we need to find prime factors, this
is the hardest part, for big number it is very hard to find all of its
prime factors, this is the security in RSA which is hard to factor a large
number.
NOTE:
1
If N is prime then phi(N) = N-1, all integers less than
N (1 to N-1) are coprime with N.
2
phi(N) is always even, both for N either composite or
prime.
3
Euler totient function is used to find the total of
primitive root of N.
4
Euler totient functions also used to find the primitive
root of N, only under multiplication (see primitive root).
Author
Site MapDisclaimer
HMaxF Ultimate Recursive Lossless Compression Research
2001 - 2002 (c) All Rights Reserved.