Problem

Source: Indian Postal Coaching 2005

Tags: number theory, greatest common divisor, algorithm, Euclidean algorithm, number theory solved



Let m,n be natural numbers and let d=gcd(m,n). Let x=2m1 and y=2n+1 (a) If md is odd, prove that gcd(x,y)=1 (b) If md is even, Find gcd(x,y)