# Proving Congruency

• January 20th 2008, 11:58 AM
Eclyps19
Proving Congruency
Prove that if n is an odd positive integer, then n^2 ≡ 1 (mod 8)

also

Show that if n|m, where n and m are positive integers greater than 1, and if a ≡ b (mod m), where a and b are integers, then a ≡ b (mod n)

Just started doing congruencies. I understand mod no problem, but I am really lost when it comes to congruencies. Any help would be great.

Thanks
• January 20th 2008, 01:46 PM
ThePerfectHacker
Quote:

Originally Posted by Eclyps19
Prove that if n is an odd positive integer, then n^2 ≡ 1 (mod 8)

You need to show 8 divides (n^2 - 1) meaning 8 divides (n+1)(n-1)

If n is odd then n = 2k+1 so (n+1) = 2(k+1) and n-1 = 2k. That means (n+1)(n-1) = 4k(k+1) now one of k or k+1 is even by pigeonhole and so this is divisible by 8.
• January 20th 2008, 06:45 PM
Soroban
Hello, Eclyps19!

Quote:

Show that if $n|m$, where $n\text{ and }m$ are positive integers greater than 1,

and if $a \equiv b\;(\text{mod }m)$, where $a\text{ and }b$ are integers, then: . $a \:\equiv\:b\;(\text{mod }n)$

Definition: . $a \:\equiv\:b\;(\text{mod }n) \quad\Longleftrightarrow\quad a - b \:=\:kn$

$"a\text{ is congruent to }b\text{, mod }n\text{" means: "the difference of }a\text{ and }b\text{ is a multiple of }n."$

We are told that: $n\text{ divides }m\text{, hence: }m = hn\text{ for some integer }h.$

We are given: . $a\:\equiv\;b\;(\text{mod }m)\quad\Rightarrow\quad a - b \:=\:km$

Since $m = hn\text{, we have: }\;a - b \:=\:k(hn) \:=\:(kh)n$

Hence: . $a - b\text{ is a multiple of }n.$

. . Therefore: . $a \:\equiv\:b\;(\text{mod } n)$