SOLUTION: not sure how to prove this? if n is odd then n^2 = 1 (mod 4) thanks!

Algebra.Com
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.
nn^2(n^2)/4n^2 (mod 4)
110 remainder 11
392 remainder 11
5256 remainder 11
74912 remainder 11
98120 remainder 11
1112130 remainder 11

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.



RELATED QUESTIONS

Let A = {n C Z | n is odd} and B = {n C Z | n^2 - 1 mod 4}. Prove that A is included in... (answered by ikleyn)
Suppose a >= 2 and n is a natural number larger than 1. How can I prove that if n is... (answered by math_tutor2020,ikleyn)
a, b, n ∈ Z with n > 1. Prove that if a ≡ b (mod n) then 2a ≡ 2b (mod... (answered by rothauserc)
Let a, b, n ∈ Z with n > 1. Prove that if a ≡ b (mod n) then 2a ≡ 2b... (answered by jim_thompson5910)
given d|n+1 and d|n^2+1 and d|2 prove that if n is odd then gcd(n+1,n^2+1) =... (answered by ikleyn)
I am doing permutation problems using the formula nPr = n!/(n-r)!. The problem I am... (answered by stanbon)
How to prove that all integers n, if n^3+5 is odd then n is... (answered by greenestamps)
3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1. What if n is... (answered by Edwin McCravy)
Let a, b, n ∈ N with n ≥ 2. If a^3 ≡ b^3 (mod n) then a ≡ b (mod... (answered by richard1234)