Question 1208954: not sure how to prove this?
if n is odd then n^2 = 1 (mod 4)
thanks!
Found 2 solutions by math_tutor2020, ikleyn:
Answer by math_tutor2020(3817)   (Show Source):
You can put this solution on YOUR website!
n = an odd integer
n = 2k+1 for some integer k
n^2 = (2k+1)^2
n^2 = 4k^2+4k+1 after using the FOIL rule
n^2 = 4*(k^2+k) + 1
n^2 = 4*integer + 1
The last equation shows that whatever n^2 happens to be, it's 1 more than a multiple of 4. This only applies when n is odd.
We have shown that (n^2)/4 gives some quotient remainder 1 when n is odd.
And also proves n^2 = 1 (mod 4) when n is odd.
Some examples.
| n | n^2 | (n^2)/4 | n^2 (mod 4) | | 1 | 1 | 0 remainder 1 | 1 | | 3 | 9 | 2 remainder 1 | 1 | | 5 | 25 | 6 remainder 1 | 1 | | 7 | 49 | 12 remainder 1 | 1 | | 9 | 81 | 20 remainder 1 | 1 | | 11 | 121 | 30 remainder 1 | 1 |
Try some other examples out for yourself.
When doing modular arithmetic, we ignore the quotient to focus on the remainder only.
Extra Credit Question: Try to prove that n^2 = 0 (mod 4) when n is even. A hint is that n = 2k.
Answer by ikleyn(52788)  (Show Source):
You can put this solution on YOUR website! .
not sure how to prove this?
if n is odd then n^2 = 1 (mod 4)
thanks!
~~~~~~~~~~~~~~~~~~~~
It is easy.
If n is odd integer number, it can be presented in the form n = 2k+1,
where k is some integer number.
Then
n^2 = (2k)^2 + 2*(2k) + 1 = 4k^2 + 4k + 1. (1)
In the right side, first addend, 4k^2, is a multiple of 4,
and the second addend 4k is a multiple of k.
Hence, the sum of the first two addends is a multiple of k.
Thus n^2 = 1 (mod 4).
At this point, the proof is complete.
In whole, this all is at the level of self-evident truths.
|
|
|
