1. ## Prove Divisibility

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?

2. 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?
$4\mid 2^2$ but $4\nmid 2$

3. Originally Posted by Drexel28
$4\mid 2^2$ but $4\nmid 2$
How should I device the question so that $n | a$? Never mind. Thanks anyway.

4. Originally Posted by Drexel28
$4\mid 2^2$ but $4\nmid 2$
Drexel,
I just realized, you can't use a counter example because postulate is a biconditional logic. It says $n|a^2$ unless $n|a$.

5. Originally Posted by novice
Drexel,
I just realized, you can't use a counter example because postulate is a biconditional logic. It says $n|a^2$ unless $n|a$.
I'm no logician but $n\mid a^2\Longleftrightarrow n\mid a$ is countered by my example.

6. Originally Posted by Drexel28
I'm no logician but $n\mid a^2\Longleftrightarrow n\mid a$ is countered by my example.
You are right; it's logically inconsistent.