$\displaystyle gcd(a,b)=20 \ \mbox{and} \ lcm(a,b)=840$

What is an easy, efficient way to do these sort of problems?

Printable View

- Jun 22nd 2010, 05:31 PMdwsmithFind a and b where a, b \in\mathbb{Z}^+
$\displaystyle gcd(a,b)=20 \ \mbox{and} \ lcm(a,b)=840$

What is an easy, efficient way to do these sort of problems? - Jun 22nd 2010, 06:05 PMchiph588@
$\displaystyle 20=2^2\cdot5 $ and $\displaystyle 840=2^3\cdot3\cdot5\cdot7 $

Also $\displaystyle (a,b)=\prod p_i^{\min(a_i,b_i)} $ and $\displaystyle [a,b]=\prod p_i^{\max(a_i,b_i)} $

So here's the prime factors we're interested in and the appropriate powers:

$\displaystyle

\begin{tabular}{|c|c|c|}\hline

p & \text{min} & \text{max}\\\hline\hline

2 & 2 & 3\\\hline

3 & 0 & 1\\\hline

5 & 1 & 1\\\hline

7 & 0 & 1\\\hline

\end{tabular}

$

So to find an $\displaystyle a $ and $\displaystyle b $, just choose an exponent from each row to assign to $\displaystyle a $ and choose the other for $\displaystyle b $.

For example we could take $\displaystyle a=2^2\cdot3\cdot5\cdot7 $, which forces $\displaystyle b=2^3\cdot5 $. - Jun 22nd 2010, 06:07 PMdwsmith
What do you mean by just choose an exponent?

- Jun 22nd 2010, 06:08 PMchiph588@
- Jun 22nd 2010, 06:11 PMdwsmith
- Jun 22nd 2010, 06:13 PMchiph588@
- Jun 22nd 2010, 06:14 PMdwsmith
Then there are 5*4=20 possibilities to try.

- Jun 22nd 2010, 06:19 PMchiph588@
- Jun 22nd 2010, 06:28 PMundefined
- Jun 22nd 2010, 06:30 PMdwsmith
- Jun 22nd 2010, 06:32 PMchiph588@
- Jun 22nd 2010, 06:35 PMdwsmith
Is there a way to do permutations of the exponents to solve all the solutions or must I just plug them in?

- Jun 22nd 2010, 06:38 PMchiph588@
- Jun 23rd 2010, 12:35 AMmelese
Here is another solution.

Since $\displaystyle gcd(a,b)=20$, you can write $\displaystyle a=20A$ and $\displaystyle b=20B$, where $\displaystyle A$ and $\displaystyle B$ are relatively prime.

Beacuse $\displaystyle ab=gcd(a,b)lcm(a,b)$, $\displaystyle 20^2AB=20\cdot840$ and then $\displaystyle AB=42=2\cdot3\cdot7$.

Now choose $\displaystyle A,B$ such that $\displaystyle (A,B)=1$. There are 8 possible ways. - Jun 23rd 2010, 05:59 AMdwsmith