Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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