# 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) $\displaystyle Q \equiv R (\bmod D)$ literally means "$\displaystyle Q$ leaves a remainder $\displaystyle R$ when divided by $\displaystyle D$"
(ii) Therefore, $\displaystyle Q= kD+R$ for some integer $\displaystyle k$
(iii) Alternately, $\displaystyle 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 $\displaystyle a \equiv b (\bmod p)$ then $\displaystyle 3a \equiv 3b (\bmod p)$, etc. So in most simple cases, you can treat congruences ($\displaystyle \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 $\displaystyle n=6$, $\displaystyle 3|n$. But $\displaystyle n^2=36 \equiv 0 (\bmod 3)$