(a) In the proof of Lemma 7.2.2 it is claimed that for some integers x, y,...

  

Transcribed Image Text:

(a) In the proof of Lemma 7.2.2 it is claimed that for some integers x, y, ax+py = 1. Based on this proof, give a different, much shorter proof of Lemma 7.2.9 that uses gcd (s, u) = 1. (b) Assume d = gcd(a, b). Prove gcd (,) = 1. (c) Given integers a, b, and m> 1, with a = b (mod m) and gcd(a, m) = 1, prove gcd(b, m) = 1 as well. (d) Prove that if a is multiplicative inverse of b in mod m then both a and b are relatively prime to m. . Lemma 7.2.2 Euclid's lemma If a prime number divides the product of two natural numbers,then it divides at least one of the numbers. .Lemma 7.2.9 kcarby)=c If s divides tu and s is relatively prime to u, then s divides t. Assume 8|(tu) and gcd (sw)=1 (a) In the proof of Lemma 7.2.2 it is claimed that for some integers x, y, ax+py = 1. Based on this proof, give a different, much shorter proof of Lemma 7.2.9 that uses gcd (s, u) = 1. (b) Assume d = gcd(a, b). Prove gcd (,) = 1. (c) Given integers a, b, and m> 1, with a = b (mod m) and gcd(a, m) = 1, prove gcd(b, m) = 1 as well. (d) Prove that if a is multiplicative inverse of b in mod m then both a and b are relatively prime to m. . Lemma 7.2.2 Euclid's lemma If a prime number divides the product of two natural numbers,then it divides at least one of the numbers. .Lemma 7.2.9 kcarby)=c If s divides tu and s is relatively prime to u, then s divides t. Assume 8|(tu) and gcd (sw)=1

Answer rating: 100% (QA)

Lemma 729 Short Proof using gcds u 1 We are given that gcdsu 1From Lemma 722there exist integers x and y such that ax py 1We want to prove that gcdas ... View the full answer