3
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user26486 May 12 '15 at 15:03
  • $\begingroup$ 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. $\endgroup$ – user26486 May 12 '15 at 20:47
  • $\begingroup$ 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. $\endgroup$ – Ramified_Minds May 12 '15 at 20:52
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is a proof by contradiction, not by contraposition. You don't assume anything false when you prove something by contrapositive. See this question. $\endgroup$ – user26486 May 12 '15 at 15:09
  • 1
    $\begingroup$ 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$. $\endgroup$ – CPM May 12 '15 at 18:11
  • 1
    $\begingroup$ I think this is beyond the level of the OP. $\endgroup$ – Ramified_Minds May 12 '15 at 20:51
  • $\begingroup$ 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. $\endgroup$ – CPM May 12 '15 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.