# Function question with mod involved

• Apr 27th 2010, 10:44 AM
moocav
Function question with mod involved
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
• Apr 27th 2010, 01:42 PM
emakarov
I assume n = 30, i.e., you are considering $\mathbb{Z}_{30}$.

Quote:

c) How many different values can f(x) take wheni) a = 2
ii) a = 3
iii) a = 5
OK, consider $f(x)=2x$ on $\mathbb{Z}_{30}$. What is the size of the image of the whole domain $\mathbb{Z}_{30}$? Can you have $f(x_1)=0$, $f(x_2)=1$, $f(x_2)=2$, $f(x_3)=3$, etc. for various $x_i$? If you can't have $f(x)=n$ for some $n\in\mathbb{Z}_{30}$ and whatever $x$, then $f$ is not invertible, i.e., you can't have a function $g$ such that $f(g(x))=x$ for all $x\in\mathbb{Z}_{30}$.

(f) Hint: $f$ should be invertible when $\gcd(a,30)=1$.