# Simple Number Theory

• May 16th 2010, 07:06 PM
FlacidCelery
Simple Number Theory
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
• May 16th 2010, 08:04 PM
roninpro

After noting that $\gcd(30,72)=6\leq N\leq 30\cdot 72=2160$, I would probably list all of my possibilities at this point: 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 27, 30, 36, 40, 45, 48, 54, 60, 72, 80, 90, 108, 120, 135, 144, 180, 216, 240, 270, 360, 432, 540, 720, 1080, 2160.

Now, 30 divides $72N$. Since $30=2\cdot 3\cdot 5$ and $72=2^3\cdot 3^2$, we must conclude that $N$ is a multiple of 5. This leaves 10, 15, 20, 30, 40, 45, 60, 80, 90, 120, 135, 180, 240, 270, 360, 540, 720, 1080, 2160.

On the other hand, 72 divides $30N$. By similar reasoning as before, $N$ must be a multiple of $2^2\cdot 3=12$. Eliminating the bad possibilities leaves 60 as the smallest number satisfying all three conditions.
• May 16th 2010, 08:30 PM
NowIsForever
8|72 so for 8 to divide 30N, 4|N. 5|30, thus 5|N, since 5∤72. 3|N since 9|72 and 9∤30. Thus N must be at minimum 2²·3·5 = 60.
• May 16th 2010, 09:49 PM
simplependulum
Consider the three numbers

$ab ~,~ bc ~,~ ca$

the set satisfies the requirement because

$(ab)(bc) = b^2 (ca)$

$(bc)(ca) = c^2 (ab)$

$(ca)(ab) = a^2 (bc)$

Let $ab = 30$ , $bc = 72$ so $N = ca$ .

To minimize $N = ca$ , we have to maximize $b$ so obviously what we are looking for is the greatest common divisor of $30$ and $72$ which is $6$

Therefore $N = 5(12) = 60$
• May 16th 2010, 10:04 PM
Soroban
Hello, FlacidCelery!

Quote:

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$ ?

We have: . $\begin{array}{ccccc}A &=&30 &=& 2\cdot3\cdot5 \\ B &=& 72 &=& 2^3\cdot3^2 \end{array}$

$A$ times $N$ is divisible by $B$: . $\frac{2\cdot3\cdot5\cdot N}{2^3\cdot3^2}$ is an integer.
This reduces to: . $\frac{5N}{12}$ . . . Hence. $N$ is a multiple of 12.

$B$ times $N$ is divisible by $A$: . $\frac{2^3\cdot3^2\cdot N}{2\cdot3\cdot5}$ is an integer.
This reduces to: . $\frac{2^2\cdot3\cdot N}{5}$ . . . Hence, $N$ is a multiple of 5.

The least number which is a multiple of 12 and a multiple of 5 is: . $N \:=\:60$

• May 17th 2010, 03:12 AM
FlacidCelery
Quote:

Originally Posted by Soroban
Hello, FlacidCelery!

We have: . $\begin{array}{ccccc}A &=&30 &=& 2\cdot3\cdot5 \\ B &=& 72 &=& 2^3\cdot3^2 \end{array}$

$A$ times $N$ is divisible by $B$: . $\frac{2\cdot3\cdot5\cdot N}{2^3\cdot3^2}$ is an integer.
This reduces to: . $\frac{5N}{12}$ . . . Hence. $N$ is a multiple of 12.

$B$ times $N$ is divisible by $A$: . $\frac{2^3\cdot3^2\cdot N}{2\cdot3\cdot5}$ is an integer.
This reduces to: . $\frac{2^2\cdot3\cdot N}{5}$ . . . Hence, $N$ is a multiple of 5.

The least number which is a multiple of 12 and a multiple of 5 is: . $N \:=\:60$

I really like this solution, it seems the more obvious to me. Thanks a lot everyone.