# HCF and LCM

• Jun 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?
• Jun 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.
• Jun 16th 2007, 10:14 PM
acc100jt
Is there any other way to solve this without guessing the answer??
• Jun 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
• Jun 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] \\
\text{Since }5\:|\:(n-2) & \Rightarrow & n-2= 5b\; \text{ for some integer }b & \Rightarrow & n \:=\:5b + 2 & [2] \\
\text{Since }8\:|\:(n-3) & \Rightarrow & n -3\:=\:8c\; \text{ for some integer }c & \Rightarrow & n \:=\:8c+3 &[3]
\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}$