Discrete Mathematics Answers

(19) Show that if n is an integer then n^2 ≡ 0 or 1 (mod 4).
(20) Use the result of Exercise (19) to show that if m is a positive integer that can be written in the form m= 4k+ 3 (where k is a nonnegative integer), then m is not the sum of the squares of two integers.

Show that if n|m, where n and m are integers greater than 1, and if a≡b(mod m), where a and b are integers, then a≡b(mod n).

Show that if a≡b(mod m) and c≡d(mod m), where a, b, c, d ϵ Z with m≥2, then a-c≡b-d(mod m).

Decide whether each of these integers is congruent to 3 modulo 7.
(a) 37
(b) 66
(c) -17
(d) -67

Suppose a and b are integers, a ≡ 11 (mod 19) and b ≡ 3 (mod 19). Find an integer c with 0≤c≤18 such that
(a)c≡13a(mod 19).
(b)c≡8b(mod 19).
(c)c≡a-b(mod 19).
(d)c≡7a+ 3b(mod 19).
(e)c≡2a^2+ 3b^2(mod 19).
(f)c≡a^3+ 4b^3(mod 19).

What time does a 24-hour clock read
(a) 100 hours after it reads 2:00?
(b) 45 hours before it reads 12:00?
(c) 168 hours after it reads 19:00?

Let A be a set, and let P(A) denote the power set of A. Prove that|A|<|P(A)|.
Hint: Proceed in two steps.
1. First show that|A| <= |P(A)|. Try defining the function g: A-> P(A) by g(a) ={a}, and verify that g is one-to-one.
2. Then show that we can't have |A|=|P(A)|. Assume not, i.e., suppose that in fact |A|=|P(A)|. Then there exists a bijection f: A->P(A). Let B={aϵA|a Ɇf(a)} ϵ P(A)

Since f is onto, there exists an a0ϵA such that f(a0) =B. How does this lead to a contradiction?

Show that if A, B, C, and D are sets with |A|=|B| and|C|=|D|, then |AxC|=|BxD|.

If A is an uncountable set and B is a countable set, must A-B be uncountable?

Show that if A and B are sets where A⊆B and A is uncountable, then B is uncountable.