1. Not finding help here? Sign up for a free 30min 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!

Modulus arithmetic proof

  1. Feb 8, 2014 #1
    1. The problem statement, all variables and given/known data
    For any integers a and b and any positive integers k and j, if ##a \equiv 2-b \pmod{k}## and ##j \mid k##, then ##a^2 + 4b - b^2 \equiv 4 \pmod{j}##


    2. Relevant equations
    ##x \equiv y\pmod{q}## then q|x-y



    3. The attempt at a solution
    At first I thought this would probably be straight forward and easy. But I got stuck a couple steps in:

    if ##a \equiv 2-b \pmod{k}## then ##k \mid a-2-b## and ##a-b-2=kn_o## (where ##n_o## is some integer). Also, if ##j \mid k## then ##k=jn_i## (where ##n_i## is an integer).

    (magic)

    I know that finally my answer should look like ##a^2 + 4b - b^2 \equiv 4 \pmod{j}## which is equivalent to ##a^2+4b-b^2-4=jn_x##

    I'm having trouble with the magic part. I know since ##k=jn_i## I can rewrite ##a-b-2=kn_o## as ##a-b-2=jn_in_o## and then replace ##n_o n_i## with ##n##. But I don't see what I should do next. It seems to me that the ##a-b-2## should get squared but I end up with too many a's when I do so. Anyway, I don't yet see the reasoning behind squaring the value to begin with.

    If anyone has a suggestion for this I'd be very appreciative.
     
  2. jcsd
  3. Feb 8, 2014 #2

    Curious3141

    User Avatar
    Homework Helper

    Start with ##a + b -2 \equiv 0 \pmod{k}##, which also implies ##a + b -2 \equiv 0 \pmod{j}##. (call this equation 1)

    Square both sides. Rearrange and manipulate until you have the exact expression you need to arrive at on the LHS. You will need to add ##a^2## to both sides at one point. Now factorise the expression on the RHS. Using equation 1, you should be able to simplify this immediately to get the required result.
     
  4. Feb 8, 2014 #3
    I didn't think we could move the b-2 over like that in these congruence problems. Our instructor made it quite clear that we couldn't treat the equivalence symbol as an equals sign.
     
  5. Feb 9, 2014 #4

    Curious3141

    User Avatar
    Homework Helper

    You cannot treat it *exactly* like an equals sign, but most arithmetic operations can be performed the same way over the modular equivalence.

    You're clearly already familiar with this (from your earlier post): If ##x \equiv y\pmod{q}## then ##q \mid (x-y)##.

    The second statement is equivalent to saying ##x - y \equiv 0 \pmod{q}## (because the remainder on dividing (x-y) by q is zero iff q divides (x-y)). Hence, you could just as easily have rearranged the first statement to get to the second statement.

    That's all I'm doing here. It's completely valid.

    The only operation that doesn't carry over neatly to modular arithmetic is division. You cannot simply divide both sides of an equivalence relation like you can in normal algebra. But there is a workaround called the multiplicative modular inverse which you can read about.
     
  6. Feb 9, 2014 #5
    I think I may have found another way while I was thinking about your method. But it hinges on my being able to square ##a \equiv b (mod k)## at the beginning. I would say something like
    if ##a \equiv 2-b ##(mod k) then ##a^2 \equiv (2-b)^2## (mod k).

    This should be true since it still follows that ##k \mid a^2-(b-2)^2##

    I don't think I have to square the k as well.
     
  7. Feb 9, 2014 #6

    Curious3141

    User Avatar
    Homework Helper

    Yes, this leads to a quicker solution. No, you shouldn't square the k as well. When in doubt always go back to what the congruence means.

    If ##x \equiv y \pmod{k}##, that means ##x = mk + y##, where m is an integer. So ##x^2 = m^2k^2 + 2mky + y^2##. If you take that expression modulo k, you can ignore all terms with k in them, giving ##x^2 \equiv y^2 \pmod{k}##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Modulus arithmetic proof
  1. Modular Arithmetic Proof (Replies: 22)

Loading...