Discrete Math - a modulus proof

In summary, the claim is that for any positive integers m and n, m and n both greater than 1, if n|m and a≡b(mod m), then a≡b(mod n). The attempt at a solution is to change each equation to a=b+qm and a=b+qn and then show that they are equal. The conclusion is that if n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c.
  • #1
CaptainSFS
58
0

Homework Statement



I have to prove the following claim.

Claim: For any positive integers m and n, m and n both greater than 1, if n|m and a≡b(mod m), then a≡b(mod n).

Homework Equations



n/a

The Attempt at a Solution



so i first changed each equation (ex: a≡b(mod m)) to a=b+qm and a=b+qn

I figured in these forms I could show that the equations are equal.

so I eventually get (a-b)/q=m or =n respectively. So I believe this shows their equality, but i am completely unsure because it won't always work I don't think. I need to also show that n|m. So tired dividing the m=(a-b)/q by the n= equation and of course I just get 1...

To be completely honest I am not quite sure how to prove this. I am not quite familiar with the mod function and I am incredibly weak with proofs. If anyone can give me insight into solving this problem I would great appreciative.

also note that this should be able to be done with a direct proof.

thanks!
 
Physics news on Phys.org
  • #2
a=b(mod m) means m|(a-b). a=b(mod n) means n|(a-b). If n|m what can you conclude from this?
 
  • #3
I guess you could conclude that (m|(a-b)) / (n|(a-b)). Or I guess that's like m|n? Actually I'm not really sure. I'm not sure if that's correct. If it is, I'm not really sure if that proves the statement. If m|n is true, does that mean they're the same integer? In which case I assume that would prove it.
 
  • #4
m|(a-b) and n|(a-b) are true/false statements. You can't DIVIDE them. Think about this. If a|b and b|c then a|c, right?
 
  • #5
Dick said:
m|(a-b) and n|(a-b) are true/false statements. You can't DIVIDE them. Think about this. If a|b and b|c then a|c, right?

Right, i mean that makes sense, but that's just reiterating the claim isn't it?

If n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c.

I think that there is some constant k so that kn=m? Then in this case, because they're modular, they come up with the same answer. Is that any more correct?
 
  • #6
Yes. I just really didn't like (m|(a-b)) / (n|(a-b)). Didn't make much sense to me. Maybe it did to you.
 
Last edited:
  • #7
I see, but this is where my weak point is. I'm not sure how I write a proof for that.
 
  • #8
"If n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c." That's the basis of the proof. Can you just flesh that out into a full proof? Start with "if n|m and a≡b(mod m)" and conclude with "then a≡b(mod n)".
 
  • #9
If a= b mod m, then m divides a- b so a-b= km for some integer k. If n divides m then m= pn for some integer p. Put those together to get that a-b= ?n.
 
  • #10
alright, thanks you two. Hopefully that'll help. I'll let you know if I have any further questions. Thanks! :)
 

FAQ: Discrete Math - a modulus proof

1. What is a modulus proof in discrete math?

A modulus proof, also known as a modular arithmetic proof, is a type of mathematical proof that uses the properties of modulus to solve problems. Modulus is a mathematical operation that finds the remainder when one number is divided by another. In discrete math, modulus proofs are often used to prove properties of numbers and to solve equations.

2. How is a modulus proof different from a traditional proof?

A modulus proof is different from a traditional proof because it relies on the properties of modulus, while a traditional proof uses logical reasoning and mathematical principles. Modulus proofs are often used in discrete math because they provide a more efficient way to solve problems involving integers.

3. What are some common applications of modulus proofs in real life?

Modulus proofs have many real-life applications, including cryptography, computer science, and engineering. In cryptography, modulus is used to create secure encryption algorithms. In computer science, modulus is used to efficiently store data in memory. In engineering, modulus is used in calculations involving stress and strain in materials.

4. Can you provide an example of a modulus proof?

Sure! One example of a modulus proof is proving that the sum of two even numbers is always even. We can represent two even numbers as 2n and 2m, where n and m are integers. When we add these two numbers, we get 2n + 2m = 2(n + m), which is still even. This is a modulus proof because we are using the property of modulus, where the remainder of any even number divided by 2 is always 0.

5. What are some tips for understanding and solving modulus proofs?

To understand and solve modulus proofs, it is important to have a strong understanding of modular arithmetic and its properties. It is also helpful to practice with different examples and familiarize yourself with common modulus equations. Additionally, breaking down the problem into smaller steps and using logical reasoning can make solving modulus proofs easier.

Similar threads

Prove every subset of countable set is either finite or else countable
Replies
1
Views
1K
Do these two statements imply an underlying induction proof?
Replies
7
Views
835
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
Replies
1
Views
989
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
Replies
4
Views
874
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
Replies
1
Views
929
Chinese Remainder theorem for 2 congruences
Replies
2
Views
1K
Problem 1-23 and 1-24 from Spivak's Calculus on Manifolds
Replies
6
Views
1K
Discrete logs and non generators
Replies
4
Views
1K
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
Replies
3
Views
1K
Bounded non-decreasing sequence is convergent
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top