Square of integers of form

Question

Prove that the square of any integer is of the form $5k, 5k+1 \text { or } 5k-1$.

Please help which theory should I use? I can't use principle of induction or division algorithm or Euclidean algorithm

By not using the division algorithm do you mean not using the result that every integer is of the form $5k$ or $5k+1 \ldots$ or $5k+4$? — Ross Millikan, Jun 06 '18 at 02:13
I think the only thing that would be possible would be proof by contradiction, but even then you would have to introduce some form of the Euclidean algorithm or the division algorithm to prove it. Without the other methods, you're pretty much hamstrung. — bjcolby15, Jun 12 '18 at 02:01

score 0 · Accepted Answer · answered Jun 06 '18 at 01:51

0

Hint: Every integer is of the form $5a$, $5a\pm1$, or $5a\pm2$. Now square these forms.

answered Jun 06 '18 at 01:51

lhf

216,483

2

That looks like the division algorithm to me. – Ross Millikan Jun 06 '18 at 02:12

score 0 · Answer 2 · answered Jun 06 '18 at 01:53

0

Let $n$ be an arbitrary positive integer and write it in the form $n=5j+c$ where $0\leq c<5$. Then, $$ n^{2}\equiv\left(5j+c\right)^{2}\equiv25j^{2}+10jc+c^{2}\equiv c^{2}\mod5. $$ Now, it's a matter of checking $c^{2}$ for each value of $c$ between 0 (inclusive) and 5 (exclusive).

answered Jun 06 '18 at 01:53

parsiad

25,154

1

Isn't your first line the division algorithm? – Ross Millikan Jun 06 '18 at 02:10
@RossMillikan: you are right – parsiad Jun 10 '18 at 16:45

Square of integers of form

2 Answers2