Z/nZ equations: "I have to prove that these are bijective in Z/77Z and give their reciprocal functions."

Mavil

New member
Joined
Jun 14, 2019
Messages
3
Hello ppl, this is my first time here. I have a question. I have to prove that these are bijective in Z/77Z and give their reciprocal functions.
1) f(x)=38x+2
2) f(x)=33x+2
3) x30

Ok so i am not trying to get the answer here without sweating for it. Warning though, i am terrible at maths.

I took case 1. f is a bijection if f is both injective and surjective.
I started by proving that f is a injection. For that i prove that f(a)=f(b)

f(a)=f(b)
38a+2=38b+2
38(a-b)=0

a=b if a-b=0 so i'm trying to find 38's inverse in Z/77Z
(-2)*38=-76 so the inverse is (-2)
-2(a-b)=0 => a-b=0 => a=b

So f is an injection
Now i want to prove that f is a surjection

y=38x+2
y-2=38x

I'm stuck here, what should i try now.
 

HallsofIvy

Elite Member
Joined
Jan 27, 2012
Messages
5,046
Where you have "-2(a- b)= 0" you should have (-2)(38)(a- b)= 0. You don't really need to do that. 77= 7(11) so the only "0 divisors" are 7 and 11. 38 has neither as a divisor so has an inverse. You don't actually have to find it. Just knowing that an inverse exists is sufficient.

From y- 3= 38x, x is y- 3 times the inverse of 38. Again, just knowing that an inverse exists (since 38 has neither 7 nor 11 as a factor) is sufficient to tell you that x is unique.
 

Mavil

New member
Joined
Jun 14, 2019
Messages
3
Wait so, going by your method, then for the 2nd f(x) since 33 has 11 as a "0 divisor" that means that it doesn't have an inverse so f is not injective and therefore not bijective?
 

HallsofIvy

Elite Member
Joined
Jan 27, 2012
Messages
5,046
Yes, 77 is 7 times 11 so adding 7 to a solution of 33x= 2 gives another solution.
If x= 0, y= 2.
If x= 7, y= 233= 3(77)+ 2= 2 (mod 77).
If x= 14, y= 464= 6(77)+ 2= 2 (mod 77).
If x= 21, y= 695= 9(77)+ 2= 2 (mod 77).
etc.
 
Last edited:

Mavil

New member
Joined
Jun 14, 2019
Messages
3
I see but since i can show that 2) is not injective i don't even have to prove the surjection since f can't be bijective if its not injective in the first place.
What about the 3rd though, is there some kind of obvious hint i'm missing.

a^30=b^30
 
Top