Two consecutive Z are relatively prime iff. their LCM=GCD.

Printable View

June 20th 2010, 03:59 PM
dwsmith

Two positive Z are relatively prime iff. their LCM=ab

Two $\mathbb{Z}^+$ are relatively prime iff. their LCM=ab.

$LCM(a,b)=\frac{ab}{GCD(a,b)}$

1. Assume a and b are relatively prime.
$GCD(a,b)=1$

$LCM(a,b)=\frac{ab}{1}=ab$

2. Assume $LCM=ab$ .
$LCM(a,b)=\frac{ab}{GCD(a,b)}\rightarrow GCD(a,b)=\frac{ab}{LCM(a,b)} \ \mbox{but since the LCM=ab} \ GCD(a,b)=1$
June 20th 2010, 04:05 PM
undefined

Quote:

Originally Posted by dwsmith

Two consecutive $\mathbb{Z}$ are relatively prime iff. their LCM=GCD.

$LCM(a,b)=\frac{ab}{GCD(a,b)}$

1. Assume a and b are relatively prime.
$GCD(a,b)=k\rightarrow k|a \ \mbox{and} \ k|b\rightarrow k|(\alpha a+\beta b)$

I am not sure if this going in the right direction.

2. Assume LCM=GCD.
Not sure how to go this direction.

I don't understand the whole setup of this problem. Two consecutive integers are always relatively prime. And consider 3 and 4. Their LCM is 12 and their GCD is 1. Are you sure you copied it out right?
June 20th 2010, 04:07 PM
dwsmith

Quote:

Originally Posted by undefined

I don't understand the whole setup of this problem. Two consecutive integers are always relatively prime. And consider 3 and 4. Their LCM is 12 and their GCD is 1. Are you sure you copied it out right?

I edited the original post. I had consecutive integers on the brain.
June 20th 2010, 04:19 PM
undefined

Quote:

Originally Posted by dwsmith

I edited the original post. I had consecutive integers on the brain.

Hmm, I'm still not seeing it. My above example of 3 and 4 still applies... when two integers are relatively prime, their GCD is 1, and the only way to have LCM equal to 1 is if both integers are 1. Am I missing something?
June 20th 2010, 04:21 PM
dwsmith

Quote:

Originally Posted by undefined

Hmm, I'm still not seeing it. My above example of 3 and 4 still applies... when two integers are relatively prime, their GCD is 1, and the only way to have LCM equal to 1 is if both integers are 1. Am I missing something?

Ok I re-edited it.
June 20th 2010, 04:46 PM
undefined

Quote:

Originally Posted by dwsmith

Ok I re-edited it.

Ohh okay it makes sense now.

My first thought is to use prime factorisations. I think the most convenient notation for prime factorisation is to use an infinite product and allow exponents to equal 0. This has the added advantage that we don't have to treat 1 as a special case.

$a=p_1^{\alpha_1}p_2^{\alpha_2}\dots=\displaystyle\ prod_{i=1}^\infty p_i^{\alpha_i}$

$b=p_1^{\beta_1}p_2^{\beta_2}\dots=\displaystyle\pr od_{i=1}^\infty p_i^{\beta_i}$

where for simplicity we let $p_1=2, p_2=3, p_3=5, \dots$

We have that

$\text{lcm}(a,b)=p_1^{\max(\alpha_1,\beta_1)}p_2^{\ max(\alpha_2,\beta_2)}\dots=\displaystyle \prod_{i=1}^\infty p_i^{\max(\alpha_i,\beta_i)}$

We also have that

$ab = \displaystyle \prod_{i=1}^\infty p_i^{\alpha_i+\beta_i}$

So we have $\text{lcm}(a,b)=ab \iff \forall i\in\mathbb{Z},i>0:\max(\alpha_i,\beta_i)=\alpha_i +\beta_i$ which is true if and only if either $\alpha_i=0$ or $\beta_i=0$ , or both. Can you show how this last part is equivalent to $a\ \text{and}\ b\ \text{are relatively prime}$ ?

(Fixed a small typo)
June 20th 2010, 04:51 PM
dwsmith

Quote:

Originally Posted by undefined

Ohh okay it makes sense now.

My first thought is to use prime factorisations. I think the most convenient notation for prime factorisation is to use an infinite product and allow exponents to equal 0. This has the added advantage that we don't have to treat 1 as a special case.

$a=p_1^{\alpha_1}p_2^{\alpha_2}\dots=\displaystyle\ prod_{i=1}^\infty p_i^{\alpha_i}$

$b=p_1^{\beta_1}p_2^{\beta_2}\dots=\displaystyle\pr od_{i=1}^\infty p_i^{\beta_i}$

I don't understand why we would say a and b are infinite products and if they are to the 0 power, wouldn't that make ever p then =1
June 20th 2010, 04:57 PM
undefined

Quote:

Originally Posted by dwsmith

I don't understand why we would say a and b are infinite products and if they are to the 0 power, wouldn't that make ever p then =1

Well consider the integer 126. The typical way to express the prime factorisation is

$126=2^1\cdot3^2\cdot7^1$

But if we instead write

$126=2^1\cdot3^2\cdot5^0\cdot7^1\cdot11^0\cdot13^0\ cdots$

this gives us flexibility when comparing the prime factorisations of two different integers, because we can just match up each corresponding index without having to use notation to indicate the highest non-zero index, etc.
June 20th 2010, 05:04 PM
dwsmith

Quote:

Originally Posted by undefined

Well consider the integer 126. The typical way to express the prime factorisation is

$126=2^1\cdot3^2\cdot7^1$

But if we instead write

$126=2^1\cdot3^2\cdot5^0\cdot7^1\cdot11^0\cdot13^0\ cdots$

this gives us flexibility when comparing the prime factorisations of two different integers, because we can just match up each corresponding index without having to use notation to indicate the highest non-zero index, etc.

I updated my first post with what I think my work. Can you let me know what you think? Thanks.
June 20th 2010, 05:05 PM
undefined

Well if we're allowed to use that $\text{lcm}(a,b)=\displaystyle\frac{ab}{\gcd(a,b)}$ then the $\Leftarrow$ direction also follows easily.

Assume $\text{lcm}(a,b)=ab$

Then $\text{lcm}(a,b)=\displaystyle\frac{ab}{\gcd(a,b)}$

$\Rightarrow ab=\displaystyle\frac{ab}{\gcd(a,b)}$

$\Rightarrow \gcd(a,b)=1$

Edit: Ah, you just changed your first post and added another post saying you changed it. Looks good.