# Thread: Find a and b where a, b \in\mathbb{Z}^+

1. ## Find a and b where a, b \in\mathbb{Z}^+

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

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

2. Originally Posted by dwsmith
$gcd(a,b)=20 \ \mbox{and} \ lcm(a,b)=840$

What is an easy, efficient way to do these sort of problems?
$20=2^2\cdot5$ and $840=2^3\cdot3\cdot5\cdot7$

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

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

$
\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 $a$ and $b$, just choose an exponent from each row to assign to $a$ and choose the other for $b$.

For example we could take $a=2^2\cdot3\cdot5\cdot7$, which forces $b=2^3\cdot5$.

3. What do you mean by just choose an exponent?

4. Originally Posted by dwsmith
What do you mean by just choose an exponent?
Choose an exponent for each row, either from the min column or the max column.

5. Originally Posted by chiph588@
Choose an exponent for each row, either from the min column or the max column.
$\forall p_i\mbox{?}$ so there are 5 to try?

6. Originally Posted by dwsmith
$\forall p_i\mbox{?}$ so there are 5 to try?
Yes, for every prime dividing the gcd or lcm. In this case we have 4 primes: 2,3,5,7.

7. Then there are 5*4=20 possibilities to try.

8. Originally Posted by dwsmith
Then there are 5*4=20 possibilities to try.
No there are $2^4=16$ solutions.

9. Originally Posted by chiph588@
No there are $2^4=16$ solutions.
Well the exponent of prime factor 5 for both a and b is always 1, so it's actually $2^3=8$ distinct pairs (a,b). Note that this number counts (420, 40) and (40, 420) as distinct.

10. Originally Posted by chiph588@
No there are $2^4=16$ solutions.

Are the possible solutions always can to be 2^{number of primes}?

11. Originally Posted by dwsmith
Are the possible solutions always can to be 2^{number of primes}?
Let a be the number of primes where $a_i\neq b_i$.

Then the number of solutions is $2^a$.

12. Is there a way to do permutations of the exponents to solve all the solutions or must I just plug them in?

13. Originally Posted by dwsmith
Is there a way to do permutations of the exponents to solve all the solutions or must just plug them in?
All possible permutations form all the solutions.

14. Here is another solution.
Since $gcd(a,b)=20$, you can write $a=20A$ and $b=20B$, where $A$ and $B$ are relatively prime.

Beacuse $ab=gcd(a,b)lcm(a,b)$, $20^2AB=20\cdot840$ and then $AB=42=2\cdot3\cdot7$.
Now choose $A,B$ such that $(A,B)=1$. There are 8 possible ways.

15. Originally Posted by melese
Here is another solution.
Since $gcd(a,b)=20$, you can write $a=20A$ and $b=20B$, where $A$ and $B$ are relatively prime.

Beacuse $ab=gcd(a,b)lcm(a,b)$, $20^2AB=20\cdot840$ and then $AB=42=2\cdot3\cdot7$.
Now choose $A,B$ such that $(A,B)=1$. There are 8 possible ways.
I see what you are doing but can you expand your example?

Page 1 of 2 12 Last