Prove Divisibility

**novice** · March 1st 2010, 01:47 PM

For any integer $a$ and $n, n | a^2$ if and only if $n | a.$

Let P: $n | a^2$
and $Q: n | a$ .

I have no trouble proving $Q \Rightarrow P$ .

I have trouble with $\sim Q \Rightarrow P$ .

I am doing it by showing that if $n \not | a$ , then $a \not = ny$ or equivalently,

$a = n y + c$ , where $y, c \in \mathbb{Z}$ and 1 $\leq c < n$ . It doesn't look too good.

How do you prove $P \Rightarrow Q$ ?

For $P \Rightarrow Q$ is it okay to prove $Q \Rightarrow \sim P$ to get the contradiction?

**Drexel28** · March 1st 2010, 02:03 PM

Originally Posted by novice

For any integer $a$ and $n, n | a^2$ if and only if $n | a.$

Let P: $n | a^2$
and $Q: n | a$ .

I have no trouble proving $Q \Rightarrow P$ .

I have trouble with $\sim Q \Rightarrow P$ .

I am doing it by showing that if $n \not | a$ , then $a \not = ny$ or equivalently,

$a = n y + c$ , where $y, c \in \mathbb{Z}$ and 1 $\leq c < n$ . It doesn't look too good.

How do you prove $P \Rightarrow Q$ ?

For $P \Rightarrow Q$ is it okay to prove $Q \Rightarrow \sim P$ to get the contradiction?