- #1

- 104

- 0

**Prove "if a^2 = 4 (mod 8) then a = 2 (mod 8)"**

## Homework Statement

For all integers a, if a

^{2}= 4 (mod 8), then a = 2 (mod 8).

## Homework Equations

a = b (mod n) means a = b + nk

where a, b, and k are integers and n is a natural number.

## The Attempt at a Solution

Since a^2 = 4 (mod 8), I wrote a^2 = 8n + 4. Then a^2 = 4(2n + 1).

This is where I got stuck... The only non-efficient method I can think of is to substitute n for some really long polynomial integer to make the square root of the equation equal 2 (mod 8). However, I believe that there should be a much more simpler and efficient approach to it. Does anyone have any tips? Thanks.