# Thread: Congruence proof, did I do it somewhat correct?

1. ## Congruence proof, did I do it somewhat correct?

I just want to see how well I did with this proof, and would like to know any corrections to make if I did it improperly, thanks!

The proof is Show if a ≡ b(mod m) and n ∈ Z+ where n | m, then a ≡ b(mod n)

suppose
a ≡ b(mod m). Then n ∈ Z+ , and a,b,m,k ∈ Z. Now suppose a=b+km, then a-b=km and km=n. Thus n|m. Then a ≡ b(mod n). Hence, if a ≡ b(mod m) then a ≡ b(mod n).

2. ## Re: Congruence proof, did I do it somewhat correct?

Originally Posted by michaelgg13
I just want to see how well I did with this proof, and would like to know any corrections to make if I did it improperly, thanks!

The proof is Show if a ≡ b(mod m) and n ∈ Z+ where n | m, then a ≡ b(mod n)

suppose
a ≡ b(mod m). Then n ∈ Z+ , and a,b,m,k ∈ Z. Now suppose a=b+km, then a-b=km and km=n. Thus n|m. Then a ≡ b(mod n). Hence, if a ≡ b(mod m) then a ≡ b(mod n).

your use of "thus n|m" is odd because you are given that n|m.

just do this

$a \equiv b (\bmod~ m) \Rightarrow \exists k \in \mathbb{Z} \ni a = km + b$

Now $n|m \Rightarrow \exists j \in \mathbb{Z} \ni m = jn$ so

$a \equiv b (\bmod~ m) \Rightarrow a = jkn + b = (jk)n + b$ and thus

$a \equiv b (\bmod ~n)$

3. ## Re: Congruence proof, did I do it somewhat correct?

Originally Posted by romsek
your use of "thus n|m" is odd because you are given that n|m.

just do this

$a \equiv b (\bmod~ m) \Rightarrow \exists k \in \mathbb{Z} \ni a = km + b$

Now $n|m \Rightarrow \exists j \in \mathbb{Z} \ni m = jn$ so

$a \equiv b (\bmod~ m) \Rightarrow a = jkn + b = (jk)n + b$ and thus

$a \equiv b (\bmod ~n)$
ahh ok, that makes more sense. thanks so much!

4. ## Re: Congruence proof, did I do it somewhat correct?

Originally Posted by michaelgg13
I just want to see how well I did with this proof, and would like to know any corrections to make if I did it improperly, thanks!

The proof is Show if a ≡ b(mod m) and n ∈ Z+ where n | m, then a ≡ b(mod n)
Here another way. You should know that if $m|n~\&~n|j$ then $m|j$.

We are given that $m|(a-b) ~\&~n|m$ so $n|(a-b)$. qed