COT3100C 01 Fall 2002 S 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 0 Thus 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 a d a 4 pts Prove that if a graph G is bipartite then every circuit of G if exists must have an even length b i e contains an even number of edges Proof Consider any circuit C e1 e2 en of G c e 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 V A B A a b c and B d e last vertex vn 1 v1 Since 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 A are 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 of this 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 t u Since the graph is connected there is a simple path X connecting vertex a to t and there is a simple path Y connecting u to a Note that the lengths of paths X and Y must be odd because otherwise vertices t and u would belong to subset A instead of subset B We now can form a circuit that connects vertex a to itself by following path X from a to t edge f from t to u then path Y from u to a Note that the length of this circuit is odd since it equals the length of X odd length of Y odd 1 This is a contradiction to the assumption that every circuit of G is of an even …
View Full Document
Unlocking...