• Support PF! Buy your school textbooks, materials and every day products Here!

Proof: Modular Arithmetic

  • Thread starter cheiney
  • Start date
  • #1
11
0

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.
 

Answers and Replies

  • #2
395
14
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.
 
  • #3
Dick
Science Advisor
Homework Helper
26,258
618

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.
 
  • #4
11
0
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:
  • #5
Dick
Science Advisor
Homework Helper
26,258
618
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:
  • Like
Likes 1 person
  • #6
11
0
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?
 
  • #7
Dick
Science Advisor
Homework Helper
26,258
618
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?
 

Related Threads on Proof: Modular Arithmetic

  • Last Post
Replies
22
Views
9K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
23
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
Top