1. ## 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

2. 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.

3. Hello, Eclyps19!

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

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

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

$\displaystyle "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: $\displaystyle n\text{ divides }m\text{, hence: }m = hn\text{ for some integer }h.$

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

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

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

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