HCF and LCM

Printable View

June 16th 2007, 09:05 PM
acc100jt

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?
June 16th 2007, 09:16 PM
tukeywilliams

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.
June 16th 2007, 10:14 PM
acc100jt

Is there any other way to solve this without guessing the answer??
June 17th 2007, 03:56 AM
topsquark

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
June 17th 2007, 06:14 AM
Soroban

Hello, acc100jt!

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

Quote:

$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}$