CSC165H1 Problem Set 2

CSC165H1 Problem Set 2
 For any concrete numbers, you may state whether one divides another, or whether a number is
prime, without proof. For example, you can write statements \3 j 12" and \15 is not prime" without
justi cation.
1. [9 marks] mod 3 Prove each of the following statements. You may use the Quotient Remainder Theorem
from the course notes.
(a) [3 marks] Every integer n satis es either 9 j n
2
or 3 j n
2  1.
(b) [3 marks] No integer n satis es n
2  2 (mod 3).
(c) [3 marks] Every integer n satis es either n
2  0 (mod 4) or n
2  1 (mod 4).
2. [6 marks] more congruence.
(a) [3 marks] Prove that if p1 and p2 are distinct primes, and a and b are any integers, then
a  b (mod p1p2) , a  b (mod p1) ^ a  b (mod p2)
(b) [3 marks] Prove that if p1 and p2 are distinct primes, and a and b are any integers, there exists exactly
one integer x that satis es:
x  a (mod p1) ^ x  b (mod p2) ^ 0  x ^ x < p1p2
Hint: If two di erent integers x1 and x2 satisfy the  rst two conditions, what can you prove about
their remainder (mod p1p2)?
3. [9 marks] alternations...
For each of the following statements, decide whether you believe it is true or false. If you believe it is
true, prove the statement. If you believe it is false, negate the statement and prove the negation.
You need to approach each part seriously. There are no marks for \proving" a false statement true, or
\proving" a true statement false.
(a) [3 marks]
8e 2 R
+; 9d 2 R
+; 8x 2 R; jxj < d ) j7xj < e
(b) [3 marks]
9d 2 R
+; 8e 2 R
+; 8x 2 R; jxj < d ) j7xj < e
(c) [3 marks]
8d 2 R
+; 9e 2 R
+; 8x 2 R; jxj < d ) j7xj < e
4. [6 marks] a prime example...
Euclid proved that there are in nitely many prime numbers, and this is the approach used in the course
notes Theorem 2.3. In the questions below you may use Exercise 2.19 on modular arithmetic, and the
divisibility of linear combinations.
Page 2/
CSC165H1, Fall 2019 Problem Set 2
(a) [3 marks] Prove there are in nitely many primes congruent to 5 (mod 6). Hint: Think about the
technique of Theorem 2.3 in the course notes, and also that there are other arithmetic manipulations
other than adding one, such as multiplying by 5.
(b) [3 marks] Prove or disprove that for any natural number n there is a natural number m that is not
prime, is larger than n, and with m  5 (mod 6).
5. [3 marks] subsets If a set S has n elements, how many subsets of size 4 does it have? Investigate this for
sets of size 0, 1, 2, 3, 4, and 5, then make a conjecture. Prove your conjecture using simple induction. You
may not use any external facts or techniques from combinatorics, but you may assume (without proof)
the fact that a set with n elements has n(n  1)(n  2)=6 subsets of size 3.
6. [3 marks] number representation Read Theorem 4.1 carefully. It claims there is at least one binary representation for any natural number. The base case explicitly gives one representation for the natural number
0. Trace through the proof to see what binary representation it guarantees for the natural number 5.
What is the representation? Explain.
Page 3