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

3. Let N denote the nonnegative integers, and Z denote the
integers. Define the function g : N→Z defined by g(k) = k/2 for
even k and g(k) = −(k + 1)/2 for odd k. Prove that g is a
bijection.
(a) Prove that g is a function.
(b) Prove that g is an injection
. (c) Prove that g is a surjection.

Let f(n) be a negligible function and k a positive integer.
Prove the following:
(a) f(√n) is negligible.
(b) f(n/k) is negligible.
(c) f(n^(1/k)) is negligible.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 8 minutes ago

asked 13 minutes ago

asked 22 minutes ago

asked 30 minutes ago

asked 44 minutes ago

asked 47 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago