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!

Proof: Modular Arithmetic

  1. Sep 18, 2013 #1
    1. The problem statement, all variables and given/known data

    I am required to prove/disprove the theorem:

    If a_1 is congruent to b_1 (mod n) and a_2 is congruent to b_2 (mod n), then (a_1)^(a_2) is congruent to (b_1)^(b_2) (mod n).



    2. Relevant equations

    a_1 is congruent to b_1(mod n) can also be expressed as b_1=a_1+q*n where q is an integer.



    3. The attempt at a solution

    "There exist q, q' which are elements of Z such that (b_1)^(b_2) = (a_1+q*n)^(a_2+q'*n).

    We can express (a_1+q*n)^(a_2+q'*n) as (a_1+q*n)^(a_2) + (a_1+q*n)^(q'*n)."

    I don't think I am heading in the right direction. Is mathematical induction needed to prove this theorem?

    Thanks in advance to anyone who can provide some insight.
     
  2. jcsd
  3. Sep 18, 2013 #2
    I'm sure you've shown that if a=b mod n, then a^c=b^c mod n in class. If you haven't, then you should start there. There might be an easier way, but that's where I would start.
     
  4. Sep 18, 2013 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The question says prove/disprove. It might not be a theorem. Try to disprove it by finding a counterexample before you try to prove it.
     
  5. Sep 18, 2013 #4
    Prior to this question, we were prompted to test the theorem 10 times, and in each case the theorem was shown to be true. So, I did *attempt* to disprove it during those 10 attempts, but in each case it seemed to hold up. I know that a-b has to be a multiple of n by the definition of congruence, so I can assume that a_1^a_2 - b_1^b_2 also has to be a multiple of n, yet every value of a_1,b_1,a_2,b_2, and n that I've tried I have been unsuccessful in disproving it. Unless I am missing something major, it seems as though the theorem holds.

    EDIT: I thought about it a little deeper and I think I might have landed on something. If a_1=0 and a_2=0 as well, a_1^a_2 should be undefined. Would that be evidence enough for the contrary?
     
    Last edited: Sep 18, 2013
  6. Sep 18, 2013 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's a start. In fact, it is probably good enough. But, say, with n=2, 0^0 is not congruent to 2^2, because it's undefined. Can you vary that a bit so everything is defined but they still aren't equal? Better yet, if you can come up with an example not involving 0, in case someone complains 0 is special?
     
    Last edited: Sep 18, 2013
  7. Sep 19, 2013 #6
    Another example could be where a_2 or b_2 was a negative integer. When a_1 is negative, the expression would result in fractions that are not contained in set Z of integers. Is this what you were possibly hinting at?
     
  8. Sep 19, 2013 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I was hoping for one with all positive integers in it. They aren't that rare, I think you might have been unlucky with your first 10 tries. What were they?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted