My Math Forum gcd(k,n+k)=1 iff gcd(n,k) =1.

 Number Theory Number Theory Math Forum

 September 24th, 2017, 02:57 PM #1 Newbie   Joined: Sep 2017 From: San Diego Posts: 8 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 d|k and d|n, it follows that d|n+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 c|k and c|n+k, it follows c|n. 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, 05: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 a|b and a|c 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 a|b and a|c 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, 05:58 AM   #3
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,091
Thanks: 2360

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Shadow89 Does it work?
I think so.

September 25th, 2017, 07:26 AM   #4
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 102
Thanks: 29

Quote:
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.

Quote:
 Originally Posted by shunya 1. GCF(a, b) = GCF(b, a - b) 1 is a theorem and is derived from If a|b and a|c then a|(b - c) when b > c
This theorem is essentially what the OP is trying to prove, so it seems inappropriate to use it in the proof.

 Tags gcdk, gcdn, iff

 Thread Tools Display Modes Linear Mode

 Contact - Home - Forums - Cryptocurrency Forum - Top