Question

When the least common multiple of two positive integers is divided by their greatest common divisor, the result is 33. If one integer is 45, what is the smallest possible value of the other integer?

Answer 1

Remember gcd(a,b)=ua+vb.

Answer 2

Means that gcd(45,b)=(5*9)+vb?

Answer 3

Is this university mathematics or what?

Answer 4

We have:
\[
\text{GCD}=ax+45b\\
33(ax+45b)=\text{LCM}\\
(ax+45b)\text{LCM}=45x
\]

Answer 5

lcm = ab/gcd

ab/gcd^2 = 33

45b/gcd^2 = 33

15b/gcd^2 = 11

Answer 6

not rly, i feel stuck after that :/

Answer 7

Do we use quadratic equation?

Answer 8

hmm?

[gcd(45, b)]^2 = 15b / 11

the LHS has to be integral and so does the RHS. for RHS to be integral, b is a multiple of 11. it is also a perfect square. is 15k a perfect square for any value of k? k = 15 seems alright to me. so b = 15k = 15 b/11 = 15 * 15 => b = 165. seems to work fine.

Answer 9

Neat :)

Answer 10

By why would b=660 not work then?

Answer 11

165 < 660

Answer 12

GCD(660,45)=15
LCM(660,45)=1980
GCD/LCM=132

Answer 13

\[15\times 660\div11=900=30^2\]

Answer 14

Ah!
30 does not divide 45.

Answer 15

restating PK's reply :


15b/gcd^2 = 11

15b = 11gcd^2

since \(11\nmid 15\), we have \(11 \mid b \implies b = 11k\)
plugging this in above equation we get
15*11k = 11gcd^2
15k = gcd^2

Answer 16

the minimum value of "k" for left hand side to be a perfect square is 15

Answer 17

165 is the right answer.

Answer 18

How many b exist though? Are there an infinite of them? How can we find a algorithm to generate all b if there are more than one?

Answer 19

1485 is another b but I have no idea how I generated it.

Answer 20

Let $n$ be the other integer, so \[\frac{\mathop{\text{lcm}}[45,n]}{\gcd(45,n)} = 33.\]

We know that $\gcd(m,n) \cdot \mathop{\text{lcm}}[m,n] = mn$ for all positive integers $m$ and $n$, so \[\gcd(45,n) \cdot \mathop{\text{lcm}}[45,n] = 45n.\] Dividing this equation by the previous equation, we get \[[\gcd(45,n)]^2 = \frac{45n}{33} = \frac{15n}{11},\] so $11 [\gcd(45,n)]^2 = 15n$.

Since 11 divides the left-hand side, 11 also divides the right-hand side, which means $n$ is divisible by 11. Also, 15 divides the right-hand side, so 15 divides the left-hand side, which means $\gcd(45,n)$ is divisible by 15. Since $45 = 3 \cdot 15$, $n$ is divisible by 15. Hence, $n$ must be divisible by $11 \cdot 15 = 165$.

Note that $\gcd(45,165) = 15$ and $\mathop{\text{lcm}}[45,165] = 495$, and $495/15 = 33$, so $n=165$ is achievable and the smallest possible value of $n$ is $\boxed{165}$.

Answer 21

I understand the question is asking for the smallest b but I want to know whether there exist other b.

Answer 22

oh.