Prove that GCD(x, n + x) = 1 if and only if GCD(x, n) = 1
Favorites|Homepage
Subscriptions | sitemap
HOME > > Prove that GCD(x, n + x) = 1 if and only if GCD(x, n) = 1

Prove that GCD(x, n + x) = 1 if and only if GCD(x, n) = 1

[From: ] [author: ] [Date: 12-01-23] [Hit: ]
......
I'm completely stumped on this proof

-
You know that gcd of two numbers x,y can be expressed in the form ax+by=gcd.
Apply this:
ax+bn+bx=1--->from the above question
x(a+b)+bn=1---->here a+b is again an integer so i will just take it as k.
kx+bn=1---->k and b are integers.

From the above equation we can say GCD(x,n)=1
Hence Proved :)

-
for the greatest common denominator to be 1 n and x would have to be prime numbers so basically it would need to be n=7 and x=13 or some other prime number hope that kinda helps
1
keywords: that,and,GCD,if,Prove,only,Prove that GCD(x, n + x) = 1 if and only if GCD(x, n) = 1
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .