Prove or Disprove

Question

(a) ∀a, b, c, m ∈ Z +, if a ≡ b (mod m), then c a ≡ c b (mod m).

(b) For any positive odd integer n, 3|n or n 2 ≡ 1 (mod 12).

Answer 1

Here are some more hints for part b.

The relevant numbers are 2, for odd numbers, and 3, for multiples of 3 [the condition 3|n means 3 divides n].

We are asked to show that for odd numbers n, either n is a multiple of 3 or n² ≡ 1 (mod 12).

Following up on Tim C's hint, consider numbers mod 12. The odd numbers are 1, 3, 5, 7, 9, 11. Of these, 3 and 9 and also multiples of 3.

We need to show that the other numbers, when squared, are congruent to 1 (mod 12).

Let's check a couple together:

5: 5² = 25 and 25 ≡ 1 (mod 12)

11: 11² = 121 and 121 ≡ 1 (mod 12)

You can similarly check 1 and 7, which are the only remaining odd numbers (mod 12) that are not multiples of 3.

Once you have checked these, you are done, because we are only making a statement about numbers mod 12.

[If one wants to show this in detail, consider n = a + 12k, so that n ≡ a (mod 12). We can show that

n² ≡ a² (mod 12) as follows:

n² = (a + 12k)² = a² + 24k + 144k²

^{but 24k ≡ 0 (mod 12)}

and 144k² ≡ 0 (mod 12)

so n² ≡ a² + 0 + 0 ≡ a² (mod 12) ]

Answer 2

Hi Reddy,

a) The definition of that modulo operator a ≡ b (mod m) means some integer k exists that satisfies km = a - b. Now multiply that equation by c: ckm = c(a-b), so (ck) m = ca - cb. Since ck certainly exists, m | ca-cb so ca ≡ cb (mod m).

b) For b, think about what it means to be a positive odd integer. What must n be congruent to (mod 12)?