# Thread: Two Simple Proofs

1. ## Two Simple Proofs

Can anyone check my proofs for these two questions:

1. Let $\displaystyle p,q,r \in \mathbb{Z}$ with $\displaystyle p,r \neq 0$. Prove that if

$\displaystyle pr | qr$ then $\displaystyle p|q$

2. Let $\displaystyle a,b,m \in \mathbb{N}$, prove (by giving a complete proof or a counter example) that, if

$\displaystyle a \equiv b \pmod m$ then $\displaystyle a^2 \equiv b^2 \pmod m$

My Attempt:

1. Since $\displaystyle pr | qr$ we know that $\displaystyle qr=mpr$for some integer m. Then if we divide both sides by r we are left with $\displaystyle q=mp$, so p|q.

Is this a correct proof?

2.
$\displaystyle a \equiv b \pmod m$ $\displaystyle \iff m | (a-b)$

a-b =mk, for some integer k.
$\displaystyle a^2 \equiv b^2 \pmod m$ $\displaystyle \iff m | (a^2-b^2)$

And $\displaystyle (a^2-b^2) = (a+b)(a-b)$

$\displaystyle (a+b)(a-b) = mk(a+b)$. So $\displaystyle m|m(ka+kb)$, and therefore $\displaystyle a \equiv b \pmod m$ implies $\displaystyle a^2 \equiv b^2 \pmod m$.

Is this right? I'm not 100% convinced if this implication always holds...

2. Originally Posted by Roam
Can anyone check my proofs for these two questions:

1. Let $\displaystyle p,q,r \in \mathbb{Z}$ with $\displaystyle p,r \neq 0$. Prove that if

$\displaystyle pr | qr$ then $\displaystyle p|q$

2. Let $\displaystyle a,b,m \in \mathbb{N}$, prove (by giving a complete proof or a counter example) that, if

$\displaystyle a \equiv b \pmod m$ then $\displaystyle a^2 \equiv b^2 \pmod m$

My Attempt:

1. Since $\displaystyle pr | qr$ we know that $\displaystyle qr=mpr$for some integer m. Then if we divide both sides by r we are left with $\displaystyle q=mp$, so p|q.

Is this a correct proof?

Yessssir.

2.
$\displaystyle a \equiv b \pmod m$ $\displaystyle \iff m | (a-b)$

a-b =mk, for some integer k.
$\displaystyle a^2 \equiv b^2 \pmod m$ $\displaystyle \iff m | (a^2-b^2)$

And $\displaystyle (a^2-b^2) = (a+b)(a-b)$

$\displaystyle (a+b)(a-b) = mk(a+b)$. So $\displaystyle m|m(ka+kb)$, and therefore $\displaystyle a \equiv b \pmod m$ implies $\displaystyle a^2 \equiv b^2 \pmod m$.

I don't understand what you did in the last lines. It's simpler:

$\displaystyle a \equiv b\bmod m\Longrightarrow a = b + km\,,\,\,k\in \mathbb{Z}\Longrightarrow a^2=b^2 +(2bk+k^2m)m\Longrightarrow a^2\equiv b^2\bmod m$

Tonio

Is this right? I'm not 100% convinced if this implication always holds...
.