Proof: Modular Arithmetic

[cheiney]

Homework Statement

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).

Homework 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.

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.

 

[johnqwertyful]

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.

 

[Dick]

Homework Statement

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).

Homework 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.

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.

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.

 

[cheiney]

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.

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?

 

[Dick]

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?

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?

 

[cheiney]

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?

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?

 

[Dick]

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?

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?