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

Printable View

Show 40 post(s) from this thread on one page

June 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?
June 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:

$<br /> \begin{tabular}{|c|c|c|}\hline<br /> p & \text{min} & \text{max}\\\hline\hline<br /> 2 & 2 & 3\\\hline<br /> 3 & 0 & 1\\\hline<br /> 5 & 1 & 1\\\hline<br /> 7 & 0 & 1\\\hline<br /> \end{tabular}<br />$

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$ .
June 22nd 2010, 06:07 PM
dwsmith

What do you mean by just choose an exponent?
June 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.
June 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?
June 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.
June 22nd 2010, 06:14 PM
dwsmith

Then there are 5*4=20 possibilities to try.
June 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.
June 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.
June 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}?
June 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$ .
June 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?
June 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.
June 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.
June 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

All times are GMT -8. The time now is 06:32 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.