Solving discrete problems — Math 2020, Spring 2005Schedule For Tuesday, February 15, 2005.1. Unique prime factorisation in the integers:(see page 126 or http://www.maths.monash.edu.au/mth3122/a4lect3.pdf )2. Modular arithmetic. (Also called congruences. Section 3.6 of book.)3. Fermat’s little theorem.This gives a quicker way to tell if a number is prime. See page 411, Theorem 10.29 in text book.QuizNext Thursday the quiz will be on modular arithmetic, with questions like:Find 4 × 6 mod 7, or find 4/5 mod 7.The answer should be 0, 1, 2, 3, 4, 5 or 6 in each case.About 3 or 4 such questions would be on the quiz.Homework Due Tuesday February 22.1. Make multiplication and division tables for the integers modulo n for n = 2, 3, 4, 5, 6, 7, 8.Example, for n = 7, make two tables, one for a × b and one for a/b. A couple of entries are filled in here:a b0 1 2 3 4 5 6012 33456 2Table for a × ba b0 1 2 3 4 5 6012 63456Table for a/bExample: in the table 2 × 5 = 10 ≡ 3 mod 7.To find 2/5 mod 7, if 2/5 ≡ x mod 7, this means 2 ≡ x × 5 mod 7.Once you’ve filled in the multiplication table, you can see that 6 × 5 ≡ 2 mod 7, so we can write 2/5 ≡ 6 mod 7.For some examples, a/b mod n might not exist.In this case, just draw a line (—) in the space in the table instead of a number.2. For an integer n, we define Z/nZ to be the set of integers modulo n, so we can write Z/nZ = {0, 1, 2, . . . , n − 1}.The rules of addition on Z/nZ are mo dulo n.Now we setZ/nZ×= {x : x ∈ Z/nZ and gcd(x, n) = 1}.Here the gcd is computed in the usual way as for integers.A. Prove the following result:If n, a and b are integers, and if a ≡ b mod n, then gcd(a, n) = gcd(b, n).B. Find the number of elements in Z/nZ×for n = 2, 3, 4, 5, 6, 7, 8, 9, 10.Note, if A is a set, the number of elements in A is usually written as #A or |A|. E.g., #(Z/11Z)×= 10.C. Prove that if p is prime, then Z/pZ×has p − 1 elements.D. What can you say about the number of elements in Z/nZ×when n is not prime?E. Find the number of elements in (Z/2nZ)×for n = 1, 2, 3, 4 do you notice a pattern?F. Find the number of elements in (Z/(3 × 5)Z)×(Z/(2 × 5)Z)×and (Z/(3 × 7)Z)×. Do you notice any pattern? Howmany elements do you think are in (Z/(p × q)Z)×for p and q primes, with p 6= q.G. For integers n, a, find a condition on a so that 1/a mod n exists.(To spot a pattern, use the tables computed in question 1, and more tables if necessary).3. Can you find an example of a number m, which is not prime, and another number a so that am−1≡ 1 mod m? Isso, give an example, if not, why not?If am−1≡ 1 mod m for all a with 1 ≤ a ≤ m − 1, can we conclude that m is prime? If so, prove this, if it’s not true,give an example.1Unique Prime Factorisation of integersStatement of the Theore m:Let x be an integer greater than 1.Ifx = pm11· pm22· · · pmrr,andx = qn11· qn22· · · qnssthenr = s,and the piand qjare the same in some order,and if pi= qj, then mi= nj.IMPORTANT:There are some more hypthesis we need about pi, qj, mi, njand r and s in the statement of this theorem. What arethey?Proof of unique prime factorisation of the integers:The proof we will look at has the following basic structure:Statement of theorem:P ∧ Q → R ∧ S ∧ T reasonProof:1. P → P1arithmetic2. P1→ A1definition3. A1∧ Q → B1previous result4. C1∨ D1∨ E1fact about integers5. C1∧ P ∧ Q → False (Contradiction) arith. & previous result6. D1∧ P ∧ Q → False (Contradiction) arith. & previous result7. ∴ P ∧ Q → E1logic (from 4—6)8. ∴ P ∧ Q → B1∧ E1logic (from 1—3 and 7)9. P ∧ Q → B2∧ E2∧ . . . Br∧ Ersame as above10. P ∧ Q → G1∧ G2. . . Gssame as above11. B1∧ · · · ∧ Br→ U counting12. G1∧ · · · ∧ Gs→ V counting13. U ∧ V → R fact about integers14. B1∧ · · · Br∧ G1∧ · · · ∧ Gs→ S restatement15. E1∧ · · · ∧ Er→ T restatement16. P ∧ Q → R ∧ S ∧ T logic (from lines 8 — 15)Q.E.D.The reasons for the steps come from the following:1) Basic definitions and arithmetic— you should be able to work out the arithmetic, and what definitions are used in these steps.2) The integers are totally ordered.This means that for any two integers a and b, either a < b, a > b or a = b. There are no other possibilities.3) The “previous results” used come from previous lectures, especially the last lecture, so should be results from thefollowing list:Theorem 1 Let p be a prime and let a and b be positive integers. Then if p|ab then p|a or p|bTheorem 2 Let p be a prime and let r be a positive integer, and let a1, a2, . . . , arbe positive integers.Then if p|a1× · · · × arthen p|aifor some i with 1 ≤ r ≤ i.Theorem 3 Let p be a prime and let r be a positive integer, and let a be a positive integer.Then if p|arthen p|a.Theorem 4If p is a prime, and if r is an integer, with r ≥ 1, and if a1, a2, . . . , arare positive integers, and m1, m2, . . . , mrarepositive integers,then if p divides am11× · · · × amrrthen p|aifor some i with 1 ≤ i ≤ r.(Note, the product am11× · · · × amrrcan also be written asrYj=1amjj.)Theorem 5If p and q are primes, then if p|q then p = q.Theorem 6If p is a prime, and if r is an integer, with r ≥ 1, and if q1, q2, . . . , qrare prime numbers, and m1, m2, . . . , mrare positiveintegers,then if p dividesrYj=1qmjj. then p = qifor some i with 1 ≤ i ≤