
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 24th, 2017, 01:57 PM  #1 
Newbie Joined: Sep 2017 From: San Diego Posts: 6 Thanks: 0  gcd(k,n+k)=1 iff gcd(n,k) =1.
First prove: if gcd(k,n+k)=1 then gcd(k,n) =1. Let gcd(k,n)=d. Show d=1 by showing d<=1 and d>=1. Since d=gcd(n,k) it follows by definition of gcd that d>=1. Now since dk and dn, it follows that dn+k. Hence d is common divisor of k and n+k. Since any common divisor is less than or equal to the gcd, d<=1. Then since d<=1 and d>=1, d=1.Therefore gcd(k,n) =1 Second prove: If gcd(k,n) =1 then gcd(k,n+k)=1. By similar reasoning let gcd(k,n+k)=c. Show c=1 by showing c<=1 and c>=1. Since c=gcd(n,n+k) it follows that c>=1. Since ck and cn+k, it follows cn. So c is common divisor of k and n+k. Then c<=1. Since c<=1 and c>=1, c=1.Therefore gcd(k,n+k) =1 I tried to show that d=1 by showing that d<=1 and d>=1. Does it work? Thanks for the comments 
September 25th, 2017, 04:16 AM  #2 
Senior Member Joined: Oct 2013 From: Far far away Posts: 422 Thanks: 18 
1. GCF(a, b) = GCF(b, a  b) 1 is a theorem and is derived from If ab and ac then a(b  c) when b > c So A) If GCF(n, n + k) = 1 then GCF( n, n + k  n) = 1 which means GCF(, n, k) = 1 Now the second part... If ab and ac then a(b + c) So, B) If GCF(n, k) = 1 then GCF(n, n + k) = 1 Combining A and B we get... GCF(n, k) = 1 iff GCF(n, n + k) = 1 
September 25th, 2017, 04:58 AM  #3 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,973 Thanks: 2295 Math Focus: Mainly analysis and algebra  
September 25th, 2017, 06:26 AM  #4 
Member Joined: Aug 2017 From: United Kingdom Posts: 97 Thanks: 28  Your proof is correct, but is a bit longer than is necessary. You can just show that the common divisors of $n$ and $k$ are precisely the common divisors of $k$ and $n + k$, which is an easy one line proof (you've pretty much done it in your argument already). This then immediately implies the result  if 1 is the largest common factor of one of these pairs, it must then be the largest common factor of the other pair. This theorem is essentially what the OP is trying to prove, so it seems inappropriate to use it in the proof. 