Discrete mathematics worksheet 2 PDF

Preview

Summary

Discrete mathematics worksheet ...

Description

Discrete Mathematics, Worksheet 2 Due on Wednesday, February 11th at 14:00. You may submit up to 24 hours late with a penalty of 5% on your mark. The worksheet has 8 problems: (1) Problems marked with (∗∗) are to be submitted and you may not ask for help from anyone except myself. (2) Problems marked with (∗) are to be submitted and you may ask for help from anyone you want. (3) Problems that have no asterisk symbol will not be marked. It is up to you whether you want to do them or submit them, however they will be considered as known problems for exams or midterm purposes. Solutions to all problems will be available three days after the deadline on Study Direct. Problem 1 (∗∗). Let a, b, c ∈ N. (1) Show that there are integers x, y with [a, b] = ax + by. (2) Explain why the diophantine equation [a, b] = ax + by has infinitely many integer solutions. (3) Explain why the equation 30 = 6x + 5y has infinitely many integer solutions and find them. (4) Show that [(a, b), (a, c)] = (a, [b, c]) Problem 2. Show that every prime other than 2 or 3 is of the form 6n + 1 or 6n + 5. Problem 3 (∗). Show that if p is a prime larger than 3, then p2 + 2 is composite. Problem 4 (∗∗). Show that there is an infinite number of primes of the form 6n + 5. Problem 5 (∗). If an − 1 is a prime, where n > 1, show that a = 2 and n is prime. Problem 6 (∗∗). If 2r + 1 is prime, show that r = 2n for some n in N. Problem 7(∗). Let a, m, n ∈ N with m < n. m n (1) Show that a2 + 1 | a2 − 1. m n (2) Show that g.c.d.(a2 + 1, a2 + 1) = 1 or 2. (3) Use (2) to show there are infinitely many primes. Problem 8. Show that there is a unique triplet (p, p + 2, p +4) so that all three numbers are all prime. 1...