# prove that if $5| n^2$ then $5|n$ by contraposition

let $n \in \mathbb{R}$ suppose $5\nmid n$ then by definition of divides n = dk+r where $d \in \mathbb{Z}^{+}$ $k \in \mathbb{Z}$ and $d \neq 5$ and $0 < r \le 5$

Can someone help me finish this proof? I was told this is the correct way to start but dont have an idea on how to finish.

• I think you'd prefer to have $n\in\mathbb{N}$ for this proof. – AMPerrine May 12 '15 at 1:03
• You've accepted a proof by contradiction, not by contraposition. – user26486 May 12 '15 at 20:08

Consider the contrapositive:

If $5 \not\mid n$, then $5 \not\mid n^2$

Suppose $5 \not\mid n$. Write $n=5q+r$ with $1 \le r \le 4$. Then $n^2=25q^2+10q+r^2=5t+r^2$.

Now, $1^2 = 1$, $2^2=4$, $3^2=9=5+4$, $4^2=16=5\cdot 3 +1$. So, in all cases, $n^2$ leaves a nonzero remainder when divided by $5$, which means that $5 \not\mid n^2$.

Suppose $5\nmid n$

Then $\exists \: k,r\in \mathbb{Z}$ s.t. $n=5k+r, 1\leq r \leq 4$.

Then $n^2=(5k+r)^2=25k^2+10kr+r^2$.

$r^2=1,4,9,$ or $16$, so $5\nmid r^2$ which implies $5\nmid n^2$.

• This is a proof by contradiction, not by contraposition. You don't assume anything false and prove it directly when you prove something by contraposition. And in fact your proof would be a proof by contraposition if you removed 'assume $5\mid n^2$' and 'which is your contradiction'. See this question. – user26486 May 12 '15 at 15:03
• Proof by contraposition: $\lnot Q\,\Rightarrow\, \lnot P$. You assumed $\lnot Q$ and $P$, then proved $\lnot P$, contradicting your assumption $P$. You're adding redundancies by applying contradiction arguments here. The question asker in the link I gave above pointed out this. Proving by contradiction is redundant if the contradiction you want to get at is $\lnot P$, since it's just contraposition; also at $Q$, since it's just a direct proof. In your case it's just contraposition. – user26486 May 12 '15 at 20:47
• Ok, thanks. I haven't studied logic so didn't know the details of which was which. I thought I may have been wrong but I think the OP's main problem was that he/she didn't know the steps in the proof, not the technicalities of the logic. I will edit my answer in the way you have suggested. – Ramified_Minds May 12 '15 at 20:52

Alternative proof: You need to show if $5 \not \mid n$, then $5 \not \mid n^2$. But $5$ is prime ($p$ is prime if $p \mid ab$ implies $p \mid a$ or $p \mid b$). So if $5\mid n\cdot n$, then $5 \mid n$ (or $5 \mid n$) in either case, you have a contradiction since $5 \not \mid n$.

• This is a proof by contradiction, not by contraposition. You don't assume anything false when you prove something by contrapositive. See this question. – user26486 May 12 '15 at 15:09
• This is a good point. Very subtle difference between the two. How about this instead: $5$ is prime, so $(5)$ is prime. The complement of a prime ideal is a saturated multiplicatively closed set. Call $S:=\mathbb{Z}-(5)$. $5 \nmid n$ means $n\in S$. Then $n^2 \in S$ since $S$ is closed under multiplication. But this means $n^2 \not \in (5)$ so $5\nmid n^2$. – CPM May 12 '15 at 18:11
• I think this is beyond the level of the OP. – Ramified_Minds May 12 '15 at 20:51
• Perhaps, but on a problem about contrapositives, why not practice even more :) It is just the contrapositive of the usual definition of prime. Usually $p$ is prime if $p\mid ab \Rightarrow p\mid a$ or $p\mid b$. Equivalently, if $p \nmid a$ and $p \nmid b$, then $p \nmid ab$. This is exactly the fact that the complement of a prime ideal is closed under multiplication. Or $5 \nmid n$ and $5\nmid n$, then $5 \nmid n \cdot n=n^2$. I just think it is worth noting that the choice of $5$ is a bit of a red herring. It is just that it is prime. – CPM May 12 '15 at 23:30