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!

Homework Help: Mod. Arithmetic Proof: I don't see flaws in my logic, but it isn't working out.

  1. Sep 3, 2011 #1
    1. The problem statement, all variables and given/known data.
    1. Let [itex]a[/itex] and [itex]b[/itex] be constant integers with [itex]a \not = 0[/itex], and let the mapping [itex]f : Z \rightarrow Z[/itex] be defined by [itex]F(x) = ax + b[/itex]. Determine all values of [itex]a[/itex] such that f is a bijection. Prove that the aforementioned values are the only possible values resulting in a bijection.

    The logic in my proof makes sense, but my conclusion that [tex] ax \cong 0 \mod a[/tex] doesn't make sense because that statement will always be true.

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Sep 4, 2011 #2


    User Avatar
    Science Advisor

    What's wrong with always being true? The only way f(x)= ax+ b will not be bijective is if there exist [itex]x_1[/itex] and [itex]x_2[/itex] such that [itex]x_1\ne x_2[/itex] but [itex]ax_1+ b= ax_2+ b[/itex]. What does that tell you about a?
  4. Sep 4, 2011 #3
    I understand that it will always be 1-1.
    But my whole issue is that you could construct a [itex]f(x) = ax + b[/itex] that is not onto. For example, consider [itex]f(x) = 4x + 3[/itex]. There is no [itex]x \in \mathbf{Z}[/itex] such that [itex]f(x) = 5[/itex].

    That's my whole problem.
  5. Sep 4, 2011 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You seem to have lost the [itex]b\mod a[/itex] term in your argument. Considering it should lead you to the correct condition.
  6. Sep 4, 2011 #5
    Thanks for point that out, I did mess up there. It should be [itex]ax - b \cong b \mod a[/itex]. I don't quite see how this helps because that implies that [itex]a[/itex] must divide [itex]ax - 2b[/itex]. I don't see how that tells me anything about what a must be. I mean it tells us that [itex]a must divide [itex]2b[/itex] for this to be true.

    But anyways, at the end of the day, we know [itex]a[/itex] must divide [tex]t - b[/itex]. The only number guaranteed to divided every integer [itex]k = t - b[/itex] for all integers [itex]t[/itex] and [itex]b[/itex] is 1. The problem is finding a mathematical argument for that. Given any other a, I could always find a number such that the function isn't a bijection.
  7. Sep 5, 2011 #6
    I apologize for double posting, but it will no longer let me edit my last post. I believe I have found a solution, but I would greatly appreciate it if you could look through it and try to find errors.


Share this great discussion with others via Reddit, Google+, Twitter, or Facebook