MathDB
One on gcds

Source: Indian Postal Coaching 2005

September 22, 2005
number theorygreatest common divisoralgorithmEuclidean algorithmnumber theory solved

Problem Statement

Let m,nm,n be natural numbers and let d=gcd(m,n)d = gcd(m,n). Let x=2m−1x = 2^{m} -1 and y=2n+1y= 2^n +1 (a) If md\frac{m}{d} is odd, prove that gcd(x,y)=1gcd(x,y) = 1 (b) If md\frac{m}{d} is even, Find gcd(x,y)gcd(x,y)
Back to ProblemsView on AoPS