Prove gcd(m,n)=1 implies gcd(2m+n,2n)=1 (n odd)

  • Thread starter Skolem
  • Start date
So it must divide 1.In summary, the conversation discusses the proof of gcd(m,n)=1 implying gcd(2m+n,2n)=1, where n is odd. The speaker mentions their understanding of basic properties of gcd and a relevant formula, but expresses difficulty in understanding the proof. The summary then goes on to explain the key steps of the proof, showing that the gcd of (2m+n,2n) must divide both m and n, and therefore must also divide gcd(m,n), ultimately leading to the conclusion that it must divide 1.
  • #1
Skolem
4
0
I've been reading through the new book "Algebra: Chapter 0" by Aluffi in my spare time, but I can't seem to get this one: Prove gcd(m,n)=1 implies gcd(2m+n,2n)=1 where n is odd.

I know the basic properties of gcd, and also about min{am + bn as a,b in Z} = gcd(m,n) and all that, but I think I'm just missing something fundamental.


Skolem
 
Physics news on Phys.org
  • #2
gcd(2m+n,2n) must divide 2n. And it must be odd, because 2m+n is odd. Therefore it must divide n. Since it divides 2m+n, it must divide m. Therefore it must divide gcd(m,n).
 

FAQ: Prove gcd(m,n)=1 implies gcd(2m+n,2n)=1 (n odd)

What is the meaning of gcd?

Gcd stands for greatest common divisor. It is the largest positive integer that divides both numbers without leaving a remainder.

What does it mean for two numbers to have a gcd of 1?

When two numbers have a gcd of 1, it means that they do not have any common factors other than 1. In other words, they are relatively prime.

How does proving gcd(m,n)=1 imply gcd(2m+n,2n)=1?

Since n is odd, it can be written as 2k+1 where k is an integer. This means that 2n = 2(2k+1) = 4k+2. By substituting this for n in gcd(2m+n,2n), we get gcd(2m+2k+1,4k+2). From this, we can see that 2 is a common factor of both numbers, so if the gcd is 1, it means that there are no other common factors and therefore gcd(2m+n,2n) = 1.

Can this statement be proven using mathematical induction?

Yes, this statement can be proven using mathematical induction. We can prove that gcd(m,n)=1 implies gcd(2m+n,2n)=1 for any odd number n by using the base case of n=1 and then assuming it holds for any odd number k and proving it for k+2.

Does this statement hold true for even numbers as well?

No, this statement does not hold true for even numbers. For example, if m=2 and n=4, then gcd(m,n)=2 but gcd(2m+n,2n)=4. Therefore, this statement only applies when n is an odd number.

Similar threads

MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
Replies
3
Views
2K
Prove that ## aa_{1}, aa_{2}, ...., aa_{n} ## is also a complete set?
Replies
14
Views
1K
Order of a^m when gcd(m,n) = 1
Replies
2
Views
2K
If p is even and q is odd, then ##\binom{p}{q}## is even
Replies
19
Views
1K
What is the proof for GCD(n.m)=1 if 2^m-1 and 2^n-1 have a common divisor of 1?
Replies
3
Views
2K
How to Prove GCD of Two Powers of 2 Minus 1?
Replies
12
Views
11K
Prove that ## x\equiv 1\pmod {2n} ##
Replies
2
Views
976
Help With Proving a is Zero Divisor Mod n iff gcd(a,n)>1
Replies
2
Views
3K
MHB What Values of m and n Make These Sets a Subspace of R^4?
Replies
1
Views
1K
Choose subset of n+1 from 2n set
Replies
7
Views
5K

Hot Threads

Recent Insights

Back
Top