17
$\begingroup$

How can we prove that every odd perfect square is congruent to $1$ modulo $8$?

$\endgroup$
1
  • 5
    $\begingroup$ try some and see what happens. $\endgroup$
    – Will Jagy
    Dec 31, 2012 at 23:47

7 Answers 7

41
$\begingroup$

Observe:

$({\pm 1})^2 \equiv ({\pm 3})^2 \equiv 1 \bmod 8 $

$\endgroup$
9
  • 4
    $\begingroup$ This is the simplest and best solution presented. $\endgroup$ Dec 31, 2012 at 23:53
  • 15
    $\begingroup$ For those who can't quickly prove this on their own, this answer might be the least understandable. $\endgroup$ Jan 1, 2013 at 1:24
  • 4
    $\begingroup$ What Todd means is that a little explanation would go a long way here. Is this even a real proof, or just proof by example? $\endgroup$ Jan 1, 2013 at 1:26
  • 9
    $\begingroup$ I've been looking at this for about 20 minutes now and trying to figure out how it constitutes a proof, and it must be really good and elegant for it to get the votes it's gotten, but I can't figure it out at all. It seems to be simply saying the first two odd perfect squares are congruent to $1($mod$ 8)$. That's clearly not a complete proof. What am I missing? More to the point, since I proved this in my head right after reading the question, and I still don't understand this answer, I wonder if the OP will understand this after not being able to prove it another way. $\endgroup$ Jan 1, 2013 at 1:45
  • 10
    $\begingroup$ @ToddWilcox, all odd numbers are one of $1, -1, 3, -3 \pmod 8.$ Put another way, all odd numbers are $1,3,5,7 \pmod 8,$ as in fact all number are among $0,1,2,3,4,5,6,7 \pmod 8.$ $\endgroup$
    – Will Jagy
    Jan 1, 2013 at 2:10
38
$\begingroup$

An odd perfect square is of the form $(2k+1)^2$. $$(2k+1)^2=4k^2+4k+1=4(k^2+k)+1$$ Since $k^2+k=k(k+1)$ is always even, $4(k^2+k)$ is always divisible by $8$. Now it follows that every odd square is congruent to $1$ modulo $8$.

In general, for any integers $m,n$ such that $m$ is odd and $n>2$, $m^{2^{n-2}}$ is congruent to $1$ modulo $2^n$. This follows directly from the fact that $U(\mathbb{Z} /2^n\mathbb{Z})\cong \mathbb{Z}_2\oplus \mathbb{Z}_{2^{n-2}} $.

$\endgroup$
17
$\begingroup$

Since the square of even and odd integers are even and odd respectively, an odd square must be of the form $(4k\pm 1)^2=16k^2\pm 8k+1=8(2k^2\pm k)+1$ for some integer $k$.

$\endgroup$
1
  • $\begingroup$ If odd squares were $3 \pmod 8,$ would that really be so bad? $\endgroup$
    – Will Jagy
    Jan 1, 2013 at 5:42
15
$\begingroup$

If $n^2$ is odd, then $n$ must be odd, hence $n=2k+1$. Now, $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$. Since $k$ and $k+1$ are consecutive integers, one of them must be even (that is, it has a factor of $2$), thus $4k(k+1)\equiv0\pmod{8}$. Now it is clear that $n^2\equiv1\pmod{8}$ for all odd integers $n$.

$\endgroup$
0
3
$\begingroup$

Just for fun, I am trying to use 3 instead of 2.

An odd perfect square is of the form $(6k\pm 1)^2$ or$(6k+3)^2$ $= 36k^2\pm 12k+1$ or $36k^2+36k+9$.

$36k^2\pm 12k+1 = 12k(3k\pm 1)+1 $. If $k$ is even, $8 | 12k$; if $k$ is odd, $3k\pm 1$ is even, so $8 | 12(3k\pm 1)$.

$36k^2+36k+9 = 36k(k+1)+9 $ and $8 | 36k(k+1)+8$ since $k(k+1)$ is even.

Not as simple, but it works.

Probably can be made to work for any odd prime $p$ by looking at $(2pk\pm 1,3,5,...,p)^2$.

$\endgroup$
1
$\begingroup$

The sum of the first n integers is n(n+1)/2. The product of any two consecutive integers is always even.

Every odd number can be written as the sum of two consecutive integers or (n-1)/2 + (n+1)/2.

The product of these two consecutive numbers is divisible by 2 (which is also the sum of the first (n-1)/2 integers). Therefore, (n2-1)/8 is an integer.

Thus, every odd perfect square is congruent to 1 modulo 8

$\endgroup$
1
  • 3
    $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Jun 24, 2022 at 13:23
0
$\begingroup$

Consider the group $$(\mathbb{Z}/8\mathbb{Z})^\times = \{[1], [3], [5], [7]\} $$ under multiplication mod 8. Then $$[1]^2 =[3]^2 = [5]^2 = [7]^2 \equiv 1 \, \,\mathrm{ mod } \, 8.$$ Since every odd integer is in exactly one of these congruence classes, every odd integer squared is 1 mod 8.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .