Results 1 to 6 of 6

Thread: Simple Number Theory

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    7

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member NowIsForever's Avatar
    Joined
    May 2010
    From
    Norman, OK
    Posts
    43
    Thanks
    1
    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 235 = 60.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 $
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    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$

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2010
    Posts
    7
    Quote Originally Posted by Soroban View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jul 8th 2011, 06:09 PM
  2. Group Theory - Sylow Theory and simple groups
    Posted in the Advanced Algebra Forum
    Replies: 16
    Last Post: May 16th 2009, 11:10 AM
  3. Simple-ish number theory stuff I think... please help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 14th 2009, 07:46 PM
  4. Simple number theory...need solutions
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Feb 12th 2009, 10:41 AM
  5. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM

Search Tags


/mathhelpforum @mathhelpforum