Solved-Problem Set 1 -Solution

1. [4 marks] Truth tables and formulas. Consider the following formula: (p _ q) ) r

1. 1. [2 marks] Write the truth table for the formula. (No need to show your calculations).

1. 2. [2 marks] Write a logically equivalent formula that doesn’t use ) or ,, in other words it uses only ^; _, or :. Show how you derived the result.

2. [10 marks] congruence

Find a natural number m congruent to 5 (mod 7), and another natural number n congruent to 2 (mod 7). Find what the product mn is congruent to (mod 7), and then make a statement about the congruence of the product of any pairs of natural numbers that have the same congruences as the m and n you found, (mod 7).

1. 1. [5 marks] Write a predicate formula that expresses your statement in the form of a universally quantied implication. If you believe the statement, prove it true. If you disbelieve the statement, prove it false.

1. 2. [5 marks] Write the converse of your formula from the previous part. If you believe the converse, prove it true. If you disbelieve the converse, prove it false.

3. [4 marks] one-to-one pigeonholes

The pigeonhole principle says, informally, that if n pigeons roost in fewer than n pigeonholes, at least one pigeonhole will be crowded with more than 1 pigeon.

To make this precise, we rst formalize the notion of un-crowded for f : D 7!R:

OneToOne(f): 8x; y 2 D; x 6= y ) f(x) 6= f(y), where f : D 7!R, jDj; jRj 2 N⁺.

Let F = ff j f : D 7!R ^ jDj > 0 ^ jRj > 0g The pigeonhole principle says that:

8f 2 F; OneToOne(f) ) jDj µ jRj

1. [4 marks] Use the pigeonhole principle to prove that if n § 2 people go to the same party, there are at least 2 people who shake hands with the same number of other people. Hint: Take the set of people at the party as your domain, dene a function that evaluates how many people each person shook hands with.

You may also use the pigeonhole principle in subsequent questions in this assignment.

4. [21 marks] modular arithmetic with primes

Let a; p be natural numbers with p prime and gcd(a; p) = 1. Let T = f1; : : : ; p 1g, the positive integers less than p.

De

ne rp(x) as the remainder after division of x by p.

Prove each of the following claims. You may use the result of an earlier claim to help prove a later claim, for example Claim (e) might help prove Claim (f). You may even use an earlier claim you haven’t proven to help prove a later claim.

4. 1. [3 marks] Claim: frp(an) j n 2 T g T . Hint: Consider the material in Characterizations in the course notes.

2. [3 marks] Claim: If n1 and n2 are distinct numbers in T , then rp(an1) =6 rp(an2). Hint: Consider the material in Characterizations in the course notes.

2. [3 marks] Claim: jfrp(an) j n 2 T gj = jT j.

2. [3 marks] Claim: frp(an) j n 2 T g = T . Hint: For nite sets A and B if A B then jBj = jB nAj+jAj.

2. [3 marks] Claim: ⁱ_i⁼₌₁^{p 1}rp(ai) = ⁱ_i⁼₌₁^{p 1}i.

2. [3 marks] Claim: rp(ap 1) = 1. Hint: You may assume, as a consequence of Example 2.18, that if for

• 2 f1; 2; : : : ; kg ai bi (mod of Example 2.14, that for any

p), then ^k1ai ^k1bi (mod p). You may also assume, as an extension k > 1, if prime p – b1 ^ p – b2 ^ ^ p – bk, then p – (b1 b2 bk).

1. 7. [3 marks] Claim: If a is an arbitrary natural number that isn’t divisible by 5, then r5(a100) = 1.

5. [6 marks] primes

Since, as shown in the course notes, there are innitely many primes, it is not possible for a consecutive sequence of composite (non-prime) natural numbers to stretch on forever. However, arbitrarily long prime-free sequences exist. On the other hand, for any natural number we can always set an upper bound on how far away the next prime can be.

Prove each of the following statements. You may use the Prime predicate.

5. 1. [3 marks] Claim: For any k 2 N there is some n 2 N such that n; n + 1; : : : ; n + k are composite. Hint: Think about (k + 2)!.

5. 2. [3 marks] Claim: For any positive natural number n there exists a prime p with n < p < n! + 2. Hint: Think about n!, and the proof of Theorem 2.3, that there are innitely many primes.