# Thread: I feel like an idiot

1. ## I feel like an idiot

Am I missing something obvious, or is this really just exhaustion method?

"Find the smallest positive integer K which is divisible by seven and which, divided by each of the integers between two and six inclusive, leaves a remainder of one. If possible, find a larger value of K."

2. Hello,
Originally Posted by Hiphopopotamus
Am I missing something obvious, or is this really just exhaustion method?

"Find the smallest positive integer K which is divisible by seven and which, divided by each of the integers between two and six inclusive, leaves a remainder of one. If possible, find a larger value of K."
Hmmm do you know the Chinese remainder theorem ?

Note that if the remainder in the division by 4 is 1, then it is 1 in the division by 2 too. Because K=4k+1=2*(2k)+1. So you don't need to bother yourself working on 2.
Same goes for K=6k'+1=3*(2k)+1

Edit : never say you're an idiot.

3. You cannot be an idiot with the screenname 'hiphopopotamus'.
Go Flight of the Conchords!

Just thought I'd say that. Sorry I can't help with your question.

4. Hello, Hiphopopotamus!

Find the smallest positive integer $\displaystyle K$ which is divisible by 7,
and which, divided by each of the integers between 2 and 6 inclusive, leaves a remainder of one.
If possible, find a larger value of $\displaystyle K$.
See if this makes sense to you . . .

The Lowest Common Multiple of {2, 3, 4, 5, 6} is 60.

Then $\displaystyle K$ is of the form: .$\displaystyle K \;=\;60m + 1$

Since $\displaystyle K$ is divisible by 7: .$\displaystyle K \:=\:7n$

And we have: .$\displaystyle 7n \:=\:60m + 1 \quad\Rightarrow\quad n \:=\:\frac{60m+1}{7} \quad\Rightarrow\quad n \:=\:8m + \frac{4m+1}{7}$

Since $\displaystyle n$ is an integer, $\displaystyle 4m+1$ must be divisible by 7.
. . The first time this happens is when $\displaystyle m = 5.$
. . The next time this happens is when $\displaystyle m = 12.$

Therefore, the smallest value is: .$\displaystyle K \;=\;60(5) + 1 \;=\;\boxed{301}$

And the next value is: .$\displaystyle K \;=\;60(12) + 1 \;=\;\boxed{721}$