# Simple Number Theory

#### FlacidCelery

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

#### roninpro

Your reasoning seems okay.

After noting that $$\displaystyle \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 $$\displaystyle 72N$$. Since $$\displaystyle 30=2\cdot 3\cdot 5$$ and $$\displaystyle 72=2^3\cdot 3^2$$, we must conclude that $$\displaystyle 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 $$\displaystyle 30N$$. By similar reasoning as before, $$\displaystyle N$$ must be a multiple of $$\displaystyle 2^2\cdot 3=12$$. Eliminating the bad possibilities leaves 60 as the smallest number satisfying all three conditions.

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

#### simplependulum

MHF Hall of Honor
Consider the three numbers

$$\displaystyle ab ~,~ bc ~,~ ca$$

the set satisfies the requirement because

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

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

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

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

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

Therefore $$\displaystyle N = 5(12) = 60$$

Swlabr

#### Soroban

MHF Hall of Honor
Hello, FlacidCelery!

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

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

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

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

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

#### FlacidCelery

Hello, FlacidCelery!

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

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

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

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

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