Simple Number Theory

May 2010
7
3
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
 
Nov 2009
485
184
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.
 
May 2010
43
3
Norman, OK
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
Jan 2009
715
427
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 \)
 
  • Like
Reactions: Swlabr

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
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\)

 
May 2010
7
3
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.