Let x be an element in Un and y size of Un Euler proved tha

Let x be an element in U(n) and y = size of U(n). Euler proved that x^y 1 (mod n). This would mean that x^y-1 mod n is the inverse of x. Find the inverse of 3 in U(32) and the inverse of 3 in U(64).

Solution

3^y-1mod32 is inverse of 3

3^y = 1 mod 32

Check y = 1 , 2 , 3 , 4 , . . . by hit and trial by last digits of cycle of 3

Multiples of 3 end with 3 , 9 , 7 , 1

y = 16

3^y = 1 mod 64

Similarly , as done above

y = 16