COT3100C-01, Fall 2002COT3100C-01, Fall 2002S. Lang Key to Assignment #5 (40 pts.) 11/14/2002 1. (10 pts.) Compute GCD(1027, 373) using Euclid’s algorithm, and find two integers t and u such that 1027 t + 373 u = GCD(1027, 373).The following steps show how the extended Euclid’s GCD algorithm is applied:1027 = 373 2 + 281 --- (1)373 = 281 1 + 92 --- (2)281 = 92 3 + 5 --- (3)92 = 5 18 + 2 --- (4)5 = 2 2 + 1 --- (5)2 = 1 2 + 0Thus, GCD(1027, 373) = 1 = 5 – 2 2 , using (5)= 5 – (92 – 5 18) 2, using (4)= 92 (–2) + 5 (1+36) = 92 (–2) + 5 37= 92 (–2) + (281 – 92 3) 37, using (3)= 281 37 + 92 (–2 – 3 37) = 281 37 + 92 (–113)= 281 37 + (373 – 281 1) (–113), using (2)= 373 (–113) + 281 (37 + 113) = 373 (–113) + 281 150= 373 (–113) + (1027 – 373 2) 150, using (1)= 1027 150 + 373 (–113 – 2 150)= 1027 150 + 373 (–413)Therefore, t = 150, and u = –413, and 1027 t + 373 u = GCD(1027, 373) = 1.2. (10 pts.) Suppose a, b, and c are positive integers. Prove that if GCD(a, b) = GCD(a, c) = 1,then GCD(a, bc) = 1. Proof: We use proof by contradiction. That is, suppose GCD(a, bc) = n > 1 --- (1). We want to prove this leads to a contradiction. From (1), n must have a prime factor p according to the fundamental theorem of arithmetic. Thus, p | a --- (2) and p | bc --- (3) because p | n and n = GCD(a, bc). Note that (3) implies p | b --- (4), or p | c --- (5). We now have two cases:(Case 1) Suppose (4) is true. Note that (4) and (2) imply that p | GCD(a, b), but since GCD(a, b)= 1, this would imply p | 1, which is a contradiction. (Case 2) Suppose (5) is true. Note that (5) and (2) imply that p | GCD(a, c), but since GCD(a, c)= 1, this would imply p | 1, which is a contradiction. Therefore, we found a contradiction in both cases.3. (10 pts.) Suppose a and b are positive integers. Consider the set S = {am + bn | m and n are integers, and am + bn > 0}. (a) (3 pts.) Prove a S and b S.Proof: Note that a = a 1 + b 0, so a S. Similarly, b = a 0 + b 1, so b S. (b) (2 pts.) Prove that GCD(a, b) S.Proof: By the extended Euclid’s GCD algorithm, there exist integers t and u such that at + bu = GCD(a, b). Thus, GCD(a, b) S.(c) (5 pts.) Prove if t S, then GCD(a, b) | t.Proof: If t S, then t = am + bn --- (1) for some integers m and n. Since GCD(a, b) | a, so a = GCD(a, b) j --- (2) for some integer j; similarly, since GCD(a, b) | b, so b = GCD(a, b) k --- (3) for some integer k. Substituting (2) and (3) into (1) yields t = GCD(a, b) jm + GCD(a, b) kn = GCD(a, b) (jm + kn).Thus, we proved GCD(a, b) | t.(Note: As a result, GCD(a, b) is the smallest element of the set S.)4. (10 pts.) A graph G = (V, E) is called a bipartite graph if there exist subsets A and B of V such that V = A B, A B = , and every edge e connects a vertex of A to a vertex of B, that is, no edges connect two vertices belong to A or two vertices belong to B. An example of a bipartite graph is given below.bcdeV = A B, A = {a, b, c} and B = {d, e}(a) (4 pts.) Prove that if a graph G is bipartite then every circuit of G (if exists) must have an even length(i.e., contains an even number of edges).Proof: Consider any circuit C = (e1, e2, …, en) of G. We assume edge e1= (v1, v2), edge e2= (v2, v3), …, edge ei= (vi, vi+1), …, en= (vn, vn+1), where v1, v2, …, vn+1, are the vertices connected by the circuit and the last vertex vn+1 = v1. aSince G = (V, E) is bipartite, let us assume V = A B is the partition of the vertex set, and let us assume v1 A (the case that v1 B can be handled similarly). Thus, vertex v2 B by the bipartite property, and v3 A, v4 B, etc., where the vertices of the circuit alternate between subsets A and B. Since the last vertex of the circuit vn+1 = v1 A, n + 1 must be odd, i.e., n is even, which proves the length of the circuit is even.(b) (6 pts.) Prove if every circuit of a connected graph G = (V, E) contains an even length, where |V| > 1, then G is a bipartite graph. Proof: Pick any vertex, call it a. Consider the two subsets A = {t G | t is connected to vertex a by a simple path of an even length}. Let B = V – A. We now prove that the two subsets A and B give the desired partition of V that makes the graph a bipartite graph. Note that V = A B and A B = , because B = V – A. We need to prove that no two vertices of Aare connected by an edge --- (1), and prove that no two vertices of B are connected by an edge --- (2). Proof of (1): Suppose the contrary. That is, suppose two vertices v and w of A are connected by an edge e = (v, w). Note that there is a path P connecting vertex a to v, and there is a path Q connecting w to a, and both P and Q have an even length, because we assumed v A and w A. Thus, we found a circuit that connects vertex a back to itself consisting of path P (from a to v), the edge e (from v to w), then the path Q (from w to a). However, the length ofthis circuit is odd because it equals the length of P + length of Q + 1. This is a contradiction to the assumption that every circuit of G is of an even length.Proof of (2): Suppose the contrary. That is, suppose two vertices t and u of B are connected by an edge f = …
View Full Document
Unlocking...