Homework requirements: [Pay Attention to strictly follow these requirements ]
• You must use knowledge and information related to chapter 1 to 8 to answer the following questions and state clearly the theorem or theory you use (write the name of the theorem or write the general formula you use)
• The theorems you can use for this assignment are: Mathematical induction; Well-ordering principle; Modular Arithmetic; Fundamental Theorem of Arithmetic; Fermat’s little theorem; Wilson’s theorem; Euler’s theorem; Euclidean algorithm; RSA method; Theorems mentioned in chapter 8 about rational and irrational numbers.
• For any question that specifically requires you to justify/show/prove with certain lemma or method, you cannot use different way to answer that otherwise you will receive zero.
• For any other equations or theorems, you have to prove them before you use them. Also, all these lemmas cannot be beyond the scope of knowledge from chapter 1 to 8.
• Note: we assume the natural number starts from 1 not 0.
Let p be a prime. Prove that a p p−1 ≡ a (mod p).
(2) (a) Find 23 53 (mod 10).
(b) Find the last two digits of 23 53 .
(3) Let p = 17 and q = 19. Suppose the encrypted message is R = 93. Given that e = 35 is the encryptor, choose a decryptor d and use it to find the original message by decoding the encrypted message. (use RSA method only)
(4) Suppose n > 1 is an odd natural number whose prime factorization is n = p α1 1 · · · p αk k , αi∈ N. Prove that 2 k divides φ(n). Hint: Use the formula for the Euler φ-function given by section 7.3 problem 27.
(5) Use Lemma 8.2.7 to prove that the product of two consecutive natural numbers is never a perfect square. That is prove that if n ∈ N then n(n + 1) is not a perfect square. [note: you have to use lemma 8.2.7 otherwise no marks, and you have to state where you need this lemma when you do your proof]
(6) Prove that for any real numbers a < b there exists an irrational number c such that a < c < b. Hint: Look at the numbers of the form q √ 2 where q is rational. You may assume that between any two different real numbers there exists a rational number.
(7) Let x = a √ 2 + b √3 5 where a, b are rational. Prove that x is rational if and only if both a = b = 0. (8) Textbook section 8.3 problem 11 (c), (e).
(9) Textbook section 8.3 problem 12.
MAS162: Foundations of Discrete Mathematics Semester 1, 2020
EXTERNAL ASSIGNMENT 4 Due by 5:00pm (AWST), Friday 15 May, 2020 Total Marks: 60
See the LMS for assignment submission instructions. Please note, in particular, that the assignment needs to be submitted (via the LMS) in the form of a single PDF file that includes not only your handwritten (or typed) working for the mathematical questions, but also your MATLAB code (propos.m) and output for the computing questions:
Q5 and Q6(b).
1. [15 marks] Write down the 2 × 2 matrices that represent the following linear transformations of the plane. Also draw the image of the (first quadrant) unit square 1 under each transformation. You can check your answers using the MATLAB program given in Example 6.3 of the Unit Notes, which you can copy from the file lintran.m (available on the LMS).
(a) A dilation with horizontal dilation factor 2 and vertical dilation factor 1/2.
(b) A vertical shear with factor −1/2. (c) A rotation of 45◦ anticlockwise. (d) A reflection across the line at angle −30◦ to the X-axis. (e) The transformation T(x, y) = (2x + 6y, x + 3y).
2. [10 marks] Write down matrices A1, A2, A3 that correspond to the respective linear transformations of the plane: T1 = “reflection across the line y = −x” T2 = ”rotation through 90◦ clockwise” T3 = ”reflection across the y axis”
(a) Use matrix multiplication to determine the geometric effect of a rotation through 90◦ clockwise followed by a reflection across the line y = −x, i.e., T2 followed by T1.
(b) Use matrix multiplication to determine the combined effect of T1 followed by T2 followed by T3.
3. [4 marks] Express (in words) the converse and contrapositive of each of the following statements.
(a) If Bob studies Mathematics, then he will get a good job.
(b) If r is a non-zero rational number, then cos r is irrational.
4. [10 marks] Calculate (by hand) the appropriate truth table to prove the following: (p ↔ q) ⇔ (p ∧ q) ∨ (¬p ∧ ¬q) Explain why your truth table shows that this proposition is valid and prove it using logical equivalences given in Tables 7.6–7.7 in the Unit Notes. [Hint: Start by using the fact that (p ↔ q) ⇔ (p → q) ∧ (q → p).] CONTINUED OVER PAGE . . .
5. [5 marks] Use the MATLAB program truth.m and a modified version of propos.m to prove or disprove the following. [(p ∧ q) ⊕ (r → s)] ⇔ [(p ∧ r) ∨ (q → s)] If it is not valid, give a counterexample; otherwise, explain why it is valid.
6. [8 marks]
(a) Use the rules of inference to prove the following: (¬p ∧ q) ∧ (r → p) ∧ (¬r → s) ∧ (s → t) ⇒ t.
(b) Use MATLAB to verify the validity of the above inference.
7. [8 marks] Express the following argument in symbolic form and test its logical validity by hand. If the argument is invalid, give a counterexample; otherwise, prove its validity using the rules of inference. If I am late for my interview, then I will not get the job. I will get the job if I interview well. I will not interview well if I am late. If I catch a taxi, I will not be late for my interview. I got the job. Therefore, I caught a taxi. ? ? ? ? ? ? ?
note: we assume the natural number starts from 1 not 0.
- Use induction to prove that the product of any three consecutive natural numbers is divisible by 6.
- Let r 6= 1 be a real number. Prove by induction that for all-natural numbers n, 1 + r + r 2 + · · · + r n = 1 − r n+1 1 − r .
- Let p be a prime. Prove that modulo p, every nonzero number has a unique multiplicative inverse. That is, if x ∈ {1, 2, 3, . . . , p− 1} then there is a unique y ∈ {1, 2, 3, . . . , p − 1} such that xy ≡ 1 mod p.
- Find all primes p such that p 2 + 2 is also prime.
- Let a, b, c ∈ Z be three integers such that a 2 + b 2 = c 2 . Prove that 3 | ab.
- Let a, b be two integers and let p, q be two distinct primes. Suppose that the two congruences x ≡ a (mod p) and x ≡ b (mod q) have a simultaneous solution x0. Prove that this solution is unique modulo pq. That is prove that if x1 is another simultaneous solution, then x0 ≡ x1 (mod pq).
- Let p and q be distinct primes. Suppose a and b are integers satisfying a ≡ b (mod p) and a ≡ b (mod q). Show that a ≡ b (mod pq).
- Let p and q be distinct primes and a a natural number relatively prime to pq. Prove that a (p−1)(q−1) ≡ 1 (mod pq). Hint: you can use Fermat’s Little Theorem and question (7).
- Find 105 101 (mod 18). Recall that by convention 105 101 means 10(5101) .
- Let p be a prime larger than 5. Prove that there is a power of p that ends with the digits 00001. Hint: consider p n modulo 105 for n ∈ N. Either all these powers are distinct modulo 105 o
- Prove by induction that every natural number n ≥ 12 can be written as a sum of 4s and 5s. Hint: It is useful to note that if a number greater than 12 is written as a sum of 4s and 5s, there must be at least three terms in that sum.
- Fix a natural number n. Use induction to prove that (1 + n) 3m − 1 is divisible by n for every m ∈ N.
- Prove that ( 1 2 )( 3 4 )· · ·( 2n−1 2n ) ≤ √ 1 3n+1 for all n ∈ N. Hint: Use induction. At one point in your proof, it may be useful to multiply by 1 in a creative way.
- Let a, b, c be integers satisfying a 2 + b 2 = c 2 . Give two proofs that abc must be even, (a) by considering various parity cases (i.e. even/odd), (b) using an argument by contradiction.
- For each natural number n > 1, find distinct natural numbers x and y such that 1 x + 1 y = 1 n .
- Let x be a real number such that x + x −1 is an integer. Prove that x n + x −n is an integer for all n ∈ N. Hint: Start by considering the case n = 2: x 2+x −2 = (x+x −1 ) 2−2