1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that 2xmodn is a bijection for all odd n

  1. Mar 1, 2015 #1
    1. State whether or not f(x) = 2x mod n is a bijection for all odd n and prove it

    2. Relevant equations


    3. The attempt at a solution
    So I'm pretty sure it is a bijection over testing it for some odd n, and the fact that gcd(2,n) = 1, thus there must exist an inverse for 2x mod n. However, I realize this proof makes no sense since I can make this argument for any function mod (a prime number) that it is a bijection, although not all functions mod prime are bijections. Any thoughts on where to go now?
     
  2. jcsd
  3. Mar 1, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Why are you worried about 'all functions'? You are only dealing with the function f(x)=2x mod n. Yes, there is an inverse for multiplication by 2 mod n where n is odd. What are you worried about?
     
  4. Mar 1, 2015 #3
    Forexample, I'm saying that you can argue that x^2 is coprime with n for all primes n. Then argue that x^2 mod n is bijective for all primes n. But that's not that case. E.g. x^2mod 7
    x=3 x^2mod7 = 9mod7 = 2mod7
    x = 4 x^2mod7 = 16mod7 = 2mod7
    Thus x^2mod7 is not bijective but I can use the exact same argument from my 2xmod(n) "proof" to say that x^2mod7 is bijective. Hence, I dont think you can argue that 2x is coprime with all odd n as automatically implying that 2xmodn is bijectgive.
     
  5. Mar 1, 2015 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The only thing those have in common is the digit '2'. f(x)=2x isn't like f(x)=x^2. 3^2 mod 7=2. 2=9 mod 7. But 3^9 mod 7=6. You can't reduce exponents mod n. Is that what you are asking?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted