Euler Totient or Phi Function

by matqkks
Tags: euler, function, number theory, teaching math, totient
matqkks is offline
Oct26-13, 09:02 AM
P: 150
What is most motivating way of introducing this function? Does it in itself have any real life applications that have an impact. I can only think of a^phi(n)=1 (mod n) which is powerful result but is this function used elsewhere.
Phys.Org News Partner Mathematics news on
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
jim mcnamara
jim mcnamara is offline
Oct26-13, 09:12 AM
Sci Advisor
PF Gold
P: 1,355
It is part of the RSA encryption scheme. Is that what you mean? ssh RSA keys which allow passwordless connections over the ssh protocol rely on RSA.

So a more general answer might be "cryptography"
rcgldr is offline
Oct26-13, 10:23 AM
HW Helper
P: 6,929
I don't know what RSA encryption uses, but if n in (a^phi(n)) mod (n) = 1 is a product of 2 or more prime numbers, then phi(n) returns the count of how many numbers from 1 to n-1 are not multiples of those prime numbers. For example, if n = 3 x 37 = 111, then phi(n) = (3-1) (37-1) = 72, so there are 72 numbers from 1 to 110 not multiples of 3 or 37. Multpilication and division of any pair of those 72 numbers will produce a result that is part of the 72 number group, but addition and subraction may produce results that are not within the group.

If n is a prime number, then phi(n) is n-1, and there is at least one "primitive" often called "alpha" where every number 1 through n-1 mod n in the field can be considered as a power of "alpha" mod n. This can be the basis for a finite field group (add, subtract, multiply, divide all produce numbers within the group). Reed Solomon error correction code can be based on this type of finite field, such as pdf417 bar codes which use n = 929.

However, most error correction code is based on polynomials with singe bit coefficients (finite field mod 2) called a generator polynomial "g". Such a polynomial can be treated as a binary integer but the mathematical operations addition and subtraction are implemented as exclusive or. A finite field uses single bit polynomials modulo a generator polynomial "g".

Part of AES encryption calculates 1/x for 8 bit polynomials modulo the 9 bit polynomial [itex]1 x^8 + 1 x^4 + 1 x^3 + 1 x + 1 [/itex] (hex 11b).

rcgldr is offline
Oct27-13, 03:58 AM
HW Helper
P: 6,929

Euler Totient or Phi Function

I forgot to mention that although (a^phi(n)) mod n = 1, phi(n) may not be the smallest value that results in (a^j) mod n = 1. Using the example in my previous post for n = 3 x 37 = 111, j is never greater than 36, regardless of a, and in the case of a = 73, j is 2: (73^2) mod 111 = 1.

Register to reply

Related Discussions
Limit of the Euler totient function Calculus 4
Euler totient puzzle Linear & Abstract Algebra 2
Euler's Totient Function Linear & Abstract Algebra 2
About Euler's totient function Linear & Abstract Algebra 2
Euler's Totient Function Proving General Math 1