What are some examples of modular arithmetic proofs involving positive integers?

In summary: 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.
  • #1
cheiney
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.
 
Physics news on Phys.org
  • #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.
 
  • #3
cheiney said:

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
Dick said:
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
cheiney said:
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
Dick said:
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
cheiney said:
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?
 

1. What is modular arithmetic?

Modular arithmetic is a branch of mathematics that deals with calculations involving remainders. It is often used in cryptography, computer science, and number theory.

2. How is modular arithmetic used in real life?

Modular arithmetic has many practical applications in daily life, such as calculating the day of the week, keeping track of time, and encrypting messages in computer security.

3. What is a modulus?

A modulus is the number that is divided by in a modular arithmetic operation. It determines the size of the "clock" in which calculations are performed.

4. What is the difference between modular arithmetic and regular arithmetic?

In regular arithmetic, numbers continue on infinitely in both positive and negative directions. In modular arithmetic, numbers are limited to a specific range determined by the modulus, and once that range is reached, the numbers "wrap around" back to the beginning.

5. What are some properties of modular arithmetic?

Some important properties of modular arithmetic include the commutative, associative, and distributive properties, as well as the fact that every number has a unique inverse modulo a given modulus. Additionally, the result of a modular arithmetic operation will always be within the range determined by the modulus.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
986
Replies
1
Views
648
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Replies
22
Views
2K
  • Math Proof Training and Practice
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Replies
35
Views
3K
  • Calculus and Beyond Homework Help
Replies
4
Views
929
Replies
8
Views
1K
Back
Top