Is the following proposition true or false Justify your conc

Is the following proposition true or false? Justify your conclusion with a counterexample or a proof. For each integer n, if n is odd, then n^2 = 1 (mod 8).

(b) Compare this proposition to the proposition in Exercise (7) from Section 3.4. Are these two propositions equivalent? Explain.

(c) Is the following proposition true or false? Justify your conclusion with a counterexample or a proof. For each integer n, if n is odd and n is not a multiple of 3, then n^2 = 1 (mod 24).

Solution

a).

If nn is an odd positive integer, then n=2k+1n=2k+1, for some integer k0k0.

(2k+1)2=4k2+4k+1=4k(k+1)+1.(2k+1)2=4k2+4k+1=4k(k+1)+1.

Clearly, 44k(k+1)44k(k+1). Now, one of the factors in k(k+1)k(k+1) is even. So 2k(k+1)2k(k+1).

That gives us (2×4)4k(k+1)(2×4)4k(k+1). So

4k(k+1)0mod84k(k+1)+11mod8

Hence, for each integer ,if n is odd ,then n^2 = 1(mod 8).

b). I dont know which exercise 7 and what section 3.4 .so, you have rechech this question part.

c).Note: The distinction between real equality and equivalence with respect to modulus arithmetic might cause concern here. I am being fussy about language here, and using the word \"congruent\" rather than \"equal\" when speaking of equivalence in modulus arithmetic. When qualified by a modulus, I use the = sign to indicate congruency.

-- end note; on to the proof: --

If n is an odd integer not divisible by 3, then it is congruent modulo 12 to 1, 5, 7, or 11. The reason is that integers congruent (again, mod 12) to any even number are even, and integers congruent to 3 or 9 (mod 12) are divisible by 3.

That means that for any such n, there is an integer k such that either
n = 12k + 1 or
n = 12k + 5 or
n = 12k + 7 or
n = 12k + 11
so we can look at n^2 for each of these cases.

(12k + 1)^2 = 144k^2 + 24k + 1 = 1 mod 24
(12k + 5)^2 = 144k^2 + 120k + 25 = 1 mod 24
(12k + 7)^2 = 144k^2 + 168k + 49 = 1 mod 24
(12k + 11)^2 = 144k^2 + 264k + 121 = 1 mod 24

This exhausts all the possible cases, so n^2 = 1 mod 24 for any such n.

(or)

Odd n not divisible by 3 are of the form 6k+-1. So

n^2 = 36k^2 +- 12k + 1 = 12k(3k +-1) +1

case 1: k even, then 12k is a multiple of 24 so n^2 is visibly a multiple of 24 plus 1.

case 2: k odd, then (3k +- 1) is even, so we have n^2 of the form 12k*even +1, which is also a multiple of 24 plus 1.

Hence ,

For each integer n, if n is odd and n is not a multiple of 3, then n^2 = 1 (mod 24).