For each of the following we have Z_100= {0,1,2,3,....,99} with a and b as an el
ID: 2901303 • Letter: F
Question
For each of the following we have Z_100= {0,1,2,3,....,99} with a and b as an element of Z_100 and f: Z_100--->Z_100 is a function defined by f(x)=ax+b(mod 100). In order words, when you compute f(x) you find the element in Z_100 that is congruent to ax+b modulo 100.
1. Prove that if a is either even or a multiple of 5, then f is not one-to-one.
2. Prove that if a is neither even nor a multiple of 5, then f is one-to-one
A write up of both separate proofs will get best answer and points. Thank you for the help
Explanation / Answer
1. If a is even or a multiple of 5 then either a=2c for some integer c or a=5d for some integer d. If a=2c then f(50)=2c*50+b=100*c+b, which is equivalent to b modulo 100. And f(100)=2c*100+b which is equivalent to b modulo 100. Therefore f(50)=f(100), but 50 is not equal to 100, so f is not 1-1.
If a=5d then f(20)=5c*20+b=b(mod 100) and f(100)=5c*100+b=b(mod 100) so f(20)=f(100) and so f is not 1-1.
2. Let f(x)=f(y) and we want to show that x=y. f(x)=f(y) means that ax+b=ay+b(mod 100). Thus ax=ay(mod 100). If a is not a multiple of 2 or 5 then gcd(a,100)=1 so we can divide by a and get x=y(mod 100) so x=y in Z_100 and we are done.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.