Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple Number Theory Problem

  1. May 16, 2010 #1
    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. jcsd
  3. May 16, 2010 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I think the best you can do is first/gcd(first, second) * second/gcd(first, second) = first * second / gcd(first, second)^2.
     
  4. May 17, 2010 #3
    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
  5. May 17, 2010 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The prime factorization of 30 is 2(3)(5) and the prime factorization of 72 is [itex]2^3(3^2)[/itex]. In order that N divide their product, which is [itex]2^4(3^3)(5)[/itex], it must have only factors of 2, 3, and 5- it must be of the form [itex](2^p)(3^q)(5^r)[/itex] 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, [itex]30N= 2^{p+1}(3^{q+1})(5^{r+1})[/itex] and that must be divisible by [itex]2^3(3^2)[/itex] 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.

    [itex]72N= 2^{p+3}3^{q+ 1}5^r[/itex] 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: [itex]N= 2^p(3^q)(5^r)[/itex] 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.
     
  6. May 17, 2010 #5
    Thank you very much for the help, it cleared up my confusion. I understand a little more now. :smile:


    -F
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simple Number Theory Problem
Loading...