Results 1 to 2 of 2

Math Help - 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,527
    Thanks
    773
    I assume n = 30, i.e., you are considering \mathbb{Z}_{30}.

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

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 9th 2011, 10:49 PM
  2. Replies: 1
    Last Post: February 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: February 2nd 2010, 12:52 PM
  4. involved derivative
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 13th 2009, 01:57 AM

Search Tags


/mathhelpforum @mathhelpforum