My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
Shadow89 is offline  
 
September 25th, 2017, 05:16 AM   #2
Senior Member
 
shunya's Avatar
 
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
shunya is offline  
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 View Post
Does it work?
I think so.
v8archie is offline  
September 25th, 2017, 07:26 AM   #4
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 102
Thanks: 29

Quote:
Originally Posted by Shadow89 View Post
...
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 View Post
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.
cjem is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
gcdk, gcdn, iff



Thread Tools
Display Modes






Copyright © 2017 My Math Forum. All rights reserved.