21-127: Concepts of Mathematics
Homework 7
• Your answers to the assigned problems below should be formatted as a PDF file and uploaded to Gradescope by Thursday, November 7 at 11:59 pm. You can access Gradescope from the Canvas page.
• Your answers to the unassigned problems are not collected. You can find solutions to these by clicking on the assignment on Canvas.
• The points for each assigned problem are listed on the right-hand side and (should) sum to 25. An extra bonus point is awarded for submissions that are typeset with LATEX.
Unassigned Problems
1. (a) Use the Euclidean Algorithm to determine gcd(1819 , 3587).
(b) Find (x, y) ∈ Z2 such that 1819x + 3587y = gcd(1819, 3587).
2. Prove that for all n ∈ N, 5n + 3 and 3n + 2 are coprime.
3. Let a, b ∈ Z, not both 0, and m ∈ Z+ . Prove that gcd(ma, mb) = m · gcd(a, b).
4. Find all integral solutions to the following linear diophantine equations, or state why none exist.
(a) 123x + 45y = 17 (b) 123x + 45y = 18
5. Prove that if a and b are relatively prime integers then gcd(a + b, a — b) = 1 or 2 with gcd(a + b, a — b) = 2 if a and b have the same parity.
Assigned Problems
1. Let a, b ∈ Z+ . Using only divisibility properties (material discussed in lecture prior to the discussion of prime factorizations), prove that gcd(a, b) · lcm[a, b] = ab. [5 pts]
2. Let a, b ∈ Z, not both 0, d = gcd(a, b), and c ∈ Z such that d j c. Fix (x0 , y0 ) ∈ Z2 such that ax0 + by0 = c.
(a) Show that for all k ∈ Z, the pair (x0 + d/bk, y0 — d/ak) is a solution to the linear Diophantine equation ax + by = c. [1 pt]
(b) Let s, t ∈ Z such that (x0 + s, y0 + t) is a solution to ax + by = c. Show that there exists k ∈ Z such that s = d/bk and t = — d/ak. [4 pts]
3. Prove that for all a, b ∈ Z+ , if a3 j b2 then a j b. [5 pts]
4. Prove that for all a, b ∈ Z+ , gcd(a + b,lcm[a, b]) = gcd(a, b). [5 pts]
5. Prove that for all p ∈ N, ifp is prime and p > 3 then p2 ≡ 1 (mod 24).
Hint: Consider using Euclid’s Lemma. [5 pts]