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

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

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

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

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

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

2. Assume $\displaystyle LCM=ab$.
$\displaystyle 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$

2. Originally Posted by dwsmith
Two consecutive $\displaystyle \mathbb{Z}$ are relatively prime iff. their LCM=GCD.

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

1. Assume a and b are relatively prime.
$\displaystyle 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?

3. 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.

4. 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?

5. 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.

6. 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.

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

$\displaystyle 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 $\displaystyle p_1=2, p_2=3, p_3=5, \dots$

We have that

$\displaystyle \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

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

So we have $\displaystyle \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 $\displaystyle \alpha_i=0$ or $\displaystyle \beta_i=0$, or both. Can you show how this last part is equivalent to $\displaystyle a\ \text{and}\ b\ \text{are relatively prime}$?

(Fixed a small typo)

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

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

$\displaystyle 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

8. 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

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

$\displaystyle 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.

9. Originally Posted by undefined
Well consider the integer 126. The typical way to express the prime factorisation is

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

$\displaystyle 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.

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

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

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

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

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

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