Results 1 to 5 of 5

Math Help - HCF and LCM

  1. #1
    Member
    Joined
    Oct 2006
    Posts
    185
    Thanks
    1

    HCF and LCM

    n is an integer.
    (n-2) is divisible by 3 and 5,
    (n-3) is divisible by 8,
    What is the smallest possible value of n??

    My solution is the following:
    (n-2)=15k, where k is an integer, since it is divisible by 3 and 5
    So (n-3)=15k-1 is divisible by 8, k=1, 2, 3, ...
    The smallest number k such that (n-3) is divisible by 8 is k=7 (*)
    i.e. n=107

    Is there any other ways to solve this without listing all the possible values of (n-3) in step (*) and determine
    whether (n-3) is divisible by 8.
    Because if the smallest k is very big, then I will have a long list of numbers b4 I can get the answer.
    Anyone can help?
    Last edited by acc100jt; June 16th 2007 at 09:20 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    you know that  3a = n-2 and  5p = n-2 .

    also you know that  8b = n-3 .

    So  n = 107 as the smallest possible value. Just guessed and checked.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2006
    Posts
    185
    Thanks
    1
    Is there any other way to solve this without guessing the answer??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,909
    Thanks
    329
    Awards
    1
    Call it an "educated guess." There may well be ways to refine this so that you can guess fewer numbers before you get to the correct answer, but you will still have to guess at a few. You aren't going to find a "plug'n'chug" answer to this kind of question.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,719
    Thanks
    635
    Hello, acc100jt!

    It can be solved without guessing
    . . and without invoking Modular Arithmetic,
    but it takes some Olympic-level gymnastics.


    n is an integer.
    (n-2) is divisible by 3 and 5,
    (n-3) is divisible by 8,
    What is the smallest possible value of n??

    \begin{array}{ccccccc}\text{Since }3\:|\:(n-2) & \Rightarrow & n-2 = 3a\; \text{ for some integer }a & \Rightarrow & n \:=\:3a + 2 & [1] \\<br />
\text{Since }5\:|\:(n-2) & \Rightarrow & n-2= 5b\; \text{ for some integer }b & \Rightarrow & n \:=\:5b + 2 & [2] \\<br />
\text{Since }8\:|\:(n-3) & \Rightarrow & n -3\:=\:8c\; \text{ for some integer }c & \Rightarrow & n \:=\:8c+3 &[3]<br />
\end{array}

    Equate [1] and [2]: . 3a + 2 \:=\:5b+2\quad\Rightarrow\quad b \,= \,\frac{3}{5}a

    Since b is an integer, a is a multiple of 5: . a \,= \,5k

    Equate [1] and [3]: . 3a + 2 \:=\:8c + 3\quad\Rightarrow\quad c \:=\:\frac{3a - 1}{8}

    Since a = 5k, we have: . c \;=\;\frac{15k-1}{8}

    . . A small detour: . 15k - 1 \;=\;8k + 7k - 8 + 7 \;=\;8(k-1) + 7(k+1)

    Hence: . c \;=\;\frac{8(k-1) + 7(k+1)}{8} \;=\;k - 1 + \frac{7(k+1)}{8}

    Since c is an integer, (k+1) is a multiple of 8.
    . . The least value is: k = 7
    . . Hence: . a \:=\:5(7)\:=\:35

    Substitute into [1]: . n \;=\;3(35) + 2\quad\Rightarrow\quad\boxed{n \;=\;107}

    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum