# Proof: Modular Arithmetic

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

Related Calculus and Beyond Homework Help News on Phys.org
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 Helper

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

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?

Last edited:
Dick
Homework Helper
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?

Last edited:
• 1 person
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