Let p P and n N and denote by Eulers function i Let a Z Show

Let p P, and n N, and denote by Euler’s -function.

(i) Let a Z. Show that: gcd(a, p^n) = 1 gcd(a, p) = 1 .

(ii) Show that (p^n) = p^n p^(n1) = (p 1)p^(n1).

As a and p to the power n are coprime

This impliess there exist x and y such that ax+p^ny=1

Also there exist no commom factors of a and p^n . As p^n has no other factir than p itself .

This means p is not a factor of a .

Thus gcd of a and p is also 1.

Inverse can be replicated in the same way. That is if a and p have no common factors

Then a and p to the power n will also have no common factors .

B) phi(n) is calculated usig formula as follows .

If n=pq where p and q are distinct primes then

Phi(n)=n(1-1/p) (1-1/q)

Now as n =p ^n so

Phi(p^n)= p^n(1-1/p)

=p^n(p-1/p)

= p^(n-1) ×(p-1)