Two Simple Proofs

**Roam** · October 26th 2009, 07:44 PM

Can anyone check my proofs for these two questions:

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

$pr | qr$ then $p|q$

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

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

My Attempt:

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

Is this a correct proof?

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

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

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

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

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

**tonio** · October 26th 2009, 08:43 PM

Originally Posted by Roam

Can anyone check my proofs for these two questions:

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

$pr | qr$ then $p|q$

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

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

My Attempt:

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

Is this a correct proof?

Yessssir.

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

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

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

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

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

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

.

Thread: Two Simple Proofs

LinkBack

Thread Tools

Display

Two Simple Proofs

Similar Math Help Forum Discussions

simple gcd proofs

a few simple proofs

Simple set proofs

simple but puzzling proofs

'simple' proofs

Search Tags