MATH-UA 120 Discrete Mathematicsc Problem Set 8
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Problem Set 8
MATH-UA 120 Discrete Mathematics
due May 5, 2023
These are to be written up and turned in to Gradescope.
LATEXInstructions: You can view the source ( .tex) file to get some more 金
examples of LATEX code. I have commented the source file in places where new
LATEX constructions are used.
Remember to change \showsolutionsfalse to \showsolutionstrue in the document’s preamble (between \documentclass{article} and \begin{document})
Assigned Problems
1.
(a) Find the integral linear combination of gcd(29341, 1739)
(b) Prove that 7 cannot be expressed as an integral linear combination of
29341 and 1739.
2.
(a) Explain why there does not exist integers a and b such that a + b = 100 and gcd(a, b) = 8?
(b) Prove that there exist infinitely many pairs of integers a and b such that a + b = 87 and gcd(a, b) = 3.
3.
(a) Let a, b, c ∈ Z such that a and b are relatively prime. Prove that if a | c and b | c, then (ab) | c.
(b) Prove why part (a) is false if a and b are not relatively prime.
4. Let G = (V, E) be a graph. Prove by induction:
The sum of the degrees of the vertices in G is twice the number of edges.
5. Suppose G is a subgraph of H . Prove or disprove:
(a) α(G) ≤ α(H)
(b) ω(G) ≤ ω(H)
2023-04-29