Finding the Smallest Possible Value of N in a Simple Number Theory Problem

[Fragment]

Positive integers 30, 72, and N have the property that the product of any two of them is divisible by the third. What is the smallest possible value of N?

Note I have not yet taken a Number Theory course.

I think I have found the solution using a bit of reasoning and some luck. N=60? I figured N could not be smaller than the gcd of 30 and 72, and could not be greater than their product. I also found a pattern for (30N)/72. Inputting 10, 15, 20, 30 for N gave a result of 25/6, 25/4, 25/3, 25/2, respectively. I figured that this converged to 25/1, which would then be my solution. N=60 indeed yields 25/1.

However, I feel that this is closer to luck than anything else, and also it is not very elegant. Can someone show me another way of doing this, perhaps something more elegant?


-F

 

[CRGreathouse]

I think the best you can do is first/gcd(first, second) * second/gcd(first, second) = first * second / gcd(first, second)^2.

 

[Fragment]

I think the best you can do is first/gcd(first, second) * second/gcd(first, second) = first * second / gcd(first, second)^2.

Why does this work?

Another solution I tried was prime factorization. A*N/B=5N/12 and B*N/A=2^2*3*N/5

Therefore N is the lowest common multiple multiple of 12 and 5, which is 60.

 

[HallsofIvy]

The prime factorization of 30 is 2(3)(5) and the prime factorization of 72 is 2^3(3^2). In order that N divide their product, which is 2^4(3^3)(5), it must have only factors of 2, 3, and 5- it must be of the form (2^p)(3^q)(5^r) with p a non-negative integer less than or equal to 4, q a non-negative integer less than or equal to 3, and r either 0 or 1.

Now, 30N= 2^{p+1}(3^{q+1})(5^{r+1}) and that must be divisible by 2^3(3^2) so p+ 1 must be larger than or equal to 3- p must be larger than or equal to 2- and q+ 1 must be larger than or equal to 2: q must be larger than or equal to 1.

72N= 2^{p+3}3^{q+ 1}5^r and that must be divisible by 2(3)(5) so p+3 must be larger than or equal to 1, which is neccesarily true since 0+ 3> 1, q+ 1 must be larger than 1, which, again, is necessarily true, and r must be larger than or equal to 1.

So we have: N= 2^p(3^q)(5^r) where p, q, and r are non-negative integers satisfying p larger than or equal to 2, q larger than or equal to 1, and r larger than or equal to 1.

We find the smallest possible value of k by taking p, q, and r to be the smallest possible.

 

[Fragment]

Thank you very much for the help, it cleared up my confusion. I understand a little more now.


-F