Question

Euler's Totient Function

Let f(n) denote Euler's totient function; thus, for a positive integer n, f(n) is the number of integers less than n which are coprime to n. For a prime p its is known that f(p^k) = p^k-p^{k-1}. For example f(27) = f(3^3) = 3^3 - 3^2 = (3^2) 2=18. In addition, it is known that f(n) is multiplicative in the sense that

f(ab) = f(a)f(b)

whenever a and b are coprime. Lastly, one has the celebrated generalization to Fermat's Little theorem which says that whenever a is coprime to n,

a^{f(n)} is congruent to 1 mod n

Now compute the following using prime factorizations: you may leave your answers in factored form.

A. f(2500)

B. 3^{1000} mod 2500.

C. f(10!) [ here ! denotes factorial]

Answer 1