Let f: Zn --> Zn, f(x) = ax mod 30, where 0 < a < 30.

Note: Z is the set integers and Zn = {0, 1, ..., n-1}

a) Write down the prime factorisation of 30

b) List all k, 0 < k < 30 such that k is coprime to 30 (ie. gcd(k,30) = 1)

c) How many different values can f(x) take when

i) a = 2

ii) a = 3

iii) a = 5

d) Deduce that if a is one of the priime factors of 30, then f is not invertible

e) Explain why f is not invertible for multples of the prime factors of 30

f) For what values of a is f invertible?

g) Suppose n > 2 is not prime, and g: Z --> Z, g(x) = bx mod n, where 0 < b < n. Make a conjecture about a condition b must satisfy in order that g is invertible.

Progress

I've done a) and b) but the rest I don't understand what they are asking me.. and I don't know how to start it off. If anyone could help in any way it would be much appreciated!

a) 30 = 2 x 3 x 5

b) Possible k : 7, 11, 13, 17, 19, 23, 29