# 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}^+
$\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 PM
chiph588@
Quote:

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

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

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

$\displaystyle \forall p_i\mbox{?}$ so there are 5 to try?
• Jun 22nd 2010, 06:13 PM
chiph588@
Quote:

Originally Posted by dwsmith
$\displaystyle \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 $\displaystyle 2^4=16$ solutions.
• Jun 22nd 2010, 06:28 PM
undefined
Quote:

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

Well the exponent of prime factor 5 for both a and b is always 1, so it's actually $\displaystyle 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 $\displaystyle 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 $\displaystyle a_i\neq b_i$.

Then the number of solutions is $\displaystyle 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 $\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 AM
dwsmith
Quote:

Originally Posted by melese
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.

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