# Simple Number Theory Problem

1. May 16, 2010

### 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

2. May 16, 2010

### CRGreathouse

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

3. May 17, 2010

### Fragment

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.

Last edited: May 17, 2010
4. May 17, 2010

### 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.

5. May 17, 2010

### Fragment

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

-F