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

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jun 22nd 2010, 05:31 PM
dwsmith
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?
• Jun 22nd 2010, 06:05 PM
chiph588@
Quote:

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$.
• Jun 22nd 2010, 06:07 PM
dwsmith
What do you mean by just choose an exponent?
• Jun 22nd 2010, 06:08 PM
chiph588@
Quote:

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.
• Jun 22nd 2010, 06:11 PM
dwsmith
Quote:

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?
• Jun 22nd 2010, 06:13 PM
chiph588@
Quote:

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.
• Jun 22nd 2010, 06:14 PM
dwsmith
Then there are 5*4=20 possibilities to try.
• Jun 22nd 2010, 06:19 PM
chiph588@
Quote:

Originally Posted by dwsmith
Then there are 5*4=20 possibilities to try.

No there are $2^4=16$ solutions.
• Jun 22nd 2010, 06:28 PM
undefined
Quote:

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.
• Jun 22nd 2010, 06:30 PM
dwsmith
Quote:

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

Are the possible solutions always can to be 2^{number of primes}?
• Jun 22nd 2010, 06:32 PM
chiph588@
Quote:

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$.
• Jun 22nd 2010, 06:35 PM
dwsmith
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 PM
chiph588@
Quote:

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.
• Jun 23rd 2010, 12:35 AM
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.
• Jun 23rd 2010, 05:59 AM
dwsmith
Quote:

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?
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last