Prove that if n is an odd positive integer, then n^2==1 (mod 8).?

Question

discrete math...yuck-- I know i use induction but I have no idea how to do it and I have a feeling that this problem could be on my test because she said to make sure to know how to do it.

Answer 1

n is an odd positive integer => n = 2k+1 (k positive integer or 0)

n² = (2k+1)² = 4k² + 4k + 1 = 4k(k + 1) +1

k(k + 1) is always EVEN (i.e. divisible by 2)
(if k even => k(k + 1) even; if k odd => (k + 1) even => k(k + 1) even)

so 4k(k + 1) is a multiple of 8 (ALWAYS DIVISIBLE BY 8).

Hence 4k(k + 1) +1 , when divided by 8, will always give remainder 1 (for any k).

By definition this means that 4k(k + 1) +1 is then congruent to 1 (mod 8),

i.e. n² is congruent to 1 (mod 8)

Hope this helps.

Answer 2

1 mod 8 = 1+8m where m is an integer so you need to show that n^2 is of this form.

If n=1 then n^2=1=1+8*0
If n=3 then n^2=9=1+8*1

For any positive integer k, 2k-1 is a positive odd number. So when using induction we are looking to show that if the result holds for k, it will hold for k+1 as well as that gives the next positive odd integer.

Assume that for some n=2k-1 that n^2=1+8m for some integer m.

(2k-1)^2=1+8m
4k^2-4k+1=1+8m
4(k^2-k)=8m
k^2-k=2m

If the result holds for k does it hold for k+1? Let m* be another integer.

[2(k+1)-1]^2=1+8m*
4(k+1)^2-4(k+1)+1=1+8m*
4(k^2+2k+1-k-1)=8m*
4(k^2+k)=8m*
k^2+k=2m*

So we have

k^2-k=2m

and

k^2+k=2m*

So 2k=2(m*-m) or k=(m*-m)

By assumption, m is an integer so m* is an integer as well, proving the result.

In fact not only does this show that n^2=1 mod 8 for positive odd integer n, since m*=m+k it shows that

n^2=(2k-1)^2=1+8m where m is the sum of the integers up to k-1.

For example:

the square of the 5th positive odd integer = 1+(1+2+3+4)*8=81. (9 is the 5th positive odd integer)

the square of the 8th postitive odd integer = 1+(1+2+3+4+5+6+7)*8=225. (15 is the 8th positive odd integer).

Answer 3

Since n is odd, n = 2m + 1 for some integer m. It follows n^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 4(m^2 + m) + 1 = 4m(m+1) + 1. But since m and m+1 are 2 consecutive integers, one of them is odd and the other is even, so that their product m(m+1) is even. Then, m(m+1) = 2k for some integer k.

Substituting in the previous expression of n^2, we get n^2 = 4 * 2k +1 = 8k + 1 => n^2 -1 = 8k, which shows 8 divides n^2 -1. So, by the definition of congruence, n^2 == 1 (mod 8)

Here, induction is not a good solution.

Answer 4

if n is abnormal, then it may be written as 2m+a million the position m is any integer (2m+a million)^2 = 4m^2 + 4m + a million = 4m(m +a million) + a million evaluate the left for m =a million, 2, 3 4(a million)(a million + a million) = 8 4(2)(2 +a million) = 8(3) 4(3)(3 + a million) = 8(3)(4) this gives you us perception to the actual undeniable actuality that 4m(m+a million) will continuously have 8 as a element on condition that both m or m+a million will be divisible via 2

Answer 5

if n is odd then n = 2k+1(n need not be positive)

n^2 = (2k+1)^2 = 4k^2+4k +1 = 4k(k+1) +1

either k or k+1 is even so product divisible by 2 so 4k(k+1) is divisible by 8 so n^2 mod 8 = 1