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 n2 or 3 j n2 1.
(b)
[3 marks] No integer n satis es n2 # 2 (mod 3).
(c)
[3 marks] Every integer n satis es either n2 # 0 (mod 4) or n2 # 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#(mod
p1 p2 ) , a # b (mod p1 ) ^ a # b (mod p2 )b
(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#(mod
p1 ) ^ x # b (mod p2 ) ^ 0 # x ^ x < p1 p2a
Hint:
If two di erent integers x1 and x2 satisfy the rst two conditions,
what can you prove about
their
remainder (mod p1 p2 )?
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]
8
2 R+ 9 2 R+ 8 2 R j j
e
(b)
[3 marks]
(c)
[3 marks]
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.
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 represen-tation 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.
