<p>I am absolutely lost.. please help</p> <p>Let u,v be in the Integers. Show th
ID: 1943222 • Letter: #
Question
<p>I am absolutely lost.. please help</p><p>Let u,v be in the Integers. Show that:</p>
<p>i) 2|u,v --> gcd(u,v) = 2gcd (u/2, v/2)</p>
<p>ii)2|u,2 does not divide v --> gcd ( u,v) = gcd (u|2, v)</p>
<p>iii) use (i) and (ii) to construct a binary Euclidean algorithm where you can also apply the fact that gcd ( u,v)= gcd ( u-v, v). Give a few examples.</p>
<p> </p>
<p> </p>
Explanation / Answer
We can write any u,v uniquely as : u = gcd(u,v) x s v = gcd(u,v) x t satisfying : gcd(s,t) = 1 i) u/2 = gcd(u/2,v/2) x s' (because 2|u,v the quantities on LHS are integers) v/2 = gcd(u/2,v/2) x t' such that gcd(s',t') = 1. multiply above two eqns by 2 : u = [2 x gcd(u/2,v/2)] x s' v = [2 x gcd(u/2,v/2)] x t' From the uniqueness of these kind of representations : it follows that gcd(u,v) = 2 gcd(u/2,v/2) ii) u = gcd(u,v) x s' v = gcd(u,v) x t' definition of prime p is if p|ab => p|a or p|b 2 is a prime number. 2|u and not v => 2|s' and not t', it cannot divide gcd(u,v) as then it will also have to divide v. so s' = 2m, u/2 = gcd(u,v) x m v = gcd(u,v) x t' gcd(2m,t) = 1 => no common factors => gcd(m,t) = 1. Uniqueness of these kind of representations give : gcd(u,v) = gcd(u/2,v) iii) Could be got from the definitions again. Try it along the first two lines and you will get it (its not that hard!) Examples : gcd(20,12) = 4 = 2 . 2 = 2.gcd(10,6) for i) gcd(20,15) = 5 = gcd(10,15) for ii) gcd(20,12) = gcd(20,20-12) = gcd(20,8) = 4 for iii) Have a good day !
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.