Results 1 to 2 of 2

Thread: Function question with mod involved

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    6

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    I assume n = 30, i.e., you are considering $\displaystyle \mathbb{Z}_{30}$.

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

    (f) Hint: $\displaystyle f$ should be invertible when $\displaystyle \gcd(a,30)=1$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Mar 9th 2011, 10:49 PM
  2. Replies: 1
    Last Post: Feb 11th 2010, 07:09 AM
  3. Can an empty set be involved in a 1-1 correspondence?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 2nd 2010, 12:52 PM
  4. involved derivative
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Jan 13th 2009, 01:57 AM

Search Tags


/mathhelpforum @mathhelpforum