# Prove that 2xmodn is a bijection for all odd n

1. Mar 1, 2015

### freshman2013

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. Mar 1, 2015

### Dick

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?

3. Mar 1, 2015

### freshman2013

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.

4. Mar 1, 2015

### Dick

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?