# Modular Proofs

• May 12th 2009, 11:41 AM
tshare1
Modular Proofs
I just can't seem to grasp modular arithmatic and I am trying to solve a few simple proofs:

* means "is congruent"

1) Prove if [m * n (mod 7)] then [m * N (mod 14)]

2) Prove if [3 | n] then [n^(2) * 1 (mod 3)]

Also does anyone know any good sites with some basic proofs like these with solutions? Any help is appreciated.
• May 12th 2009, 02:54 PM
Media_Man
Modular Arithmetic
A few basic rules for ya:

(i) $Q \equiv R (\bmod D)$ literally means " $Q$ leaves a remainder $R$ when divided by $D$"
(ii) Therefore, $Q= kD+R$ for some integer $k$
(iii) Alternately, $D|(Q-R)$
(iv) The nice thing about modular arithmetic is that it follows pretty much all the same rules as regular arithmetic. For example, if $a \equiv b (\bmod p)$ then $3a \equiv 3b (\bmod p)$, etc. So in most simple cases, you can treat congruences ( $\equiv$) like regular equations.

Quote:

1) Prove if [m * n (mod 7)] then [m * N (mod 14)]
What is N? Does n=N?

Quote:

2) Prove if [3 | n] then [n^(2) * 1 (mod 3)]
This statement is false. Counterexample: For $n=6$, $3|n$. But $n^2=36 \equiv 0 (\bmod 3)$