2
$\begingroup$

Is there specific set of steps to be followed when solving similar questions?

My attempt:

A number gives remainder 3 when divided by 4. Hence it is of the form 4m+3 where m = 0,1,2…

Now, 4m+3 gives remainder 4 when divided by 5. It means (4m+3)-4 is divisible by 5.

Hence, 4m-1=5n where n is some positive integer. n=(4m-1)/5.

But, 4m+3 gives remainder 5 when divided by 6. It means (4m+3)-5 is divisible by 6.

Hence, 4m-2=6f where f is some positive integer. f=(4m-2)/6.

Again, 4m+3 gives remainder 6 when divided by 7. It means (4m+3)-6 is divisible by 7.

Hence, 4m-3=7l where l is some positive integer. l=(4m-3)/7.

My confusion: What do I do now? Or am I even in the right path?

Please don't solve it using modular arithmetic. I don't know it yet.

$\endgroup$
  • $\begingroup$ This is a repeated direct application of the chinese remainder theorem. This is a special case however that should be straightforward to solve. Notice that $3=4-1$ that $4=5-1$, that $5=6-1$ etc... so you are looking for a number which satisfies $\begin{cases}n\equiv -1\pmod{4}\\n\equiv -1\pmod{5}\\n\equiv -1\pmod{6}\\n\equiv -1\pmod{7}\end{cases}$. A clear candidate would be $-1$. If you want it to be positive, then consider adding $\text{lcm}(4,5,6,7)$. $\endgroup$ – JMoravitz Jan 31 at 4:11
  • 1
    $\begingroup$ "Please don't solve using modular arithmetic" There is no time like the present to learn. It works just like ordinary arithmetic with most of the same rules that you are already familiar with, just requiring a little bit more abstraction. All you need to know about it can be learned in 2 minutes. $\endgroup$ – JMoravitz Jan 31 at 4:13
  • $\begingroup$ " Please don't solve it using modular arithmetic. I don't know it yet." Then learn it. It's exceedingly easy and will be much easier to learn it a solve this using modular arithmetic then to solve it any other way. There is no reason it should take anyone more than a half hour to learn modular arithmetic. $\endgroup$ – fleablood Jan 31 at 4:37
  • $\begingroup$ Okay.. 😊 @JMoravitz $\endgroup$ – salsabil.raisa Jan 31 at 4:38
  • $\begingroup$ Ok, going to give a shot @fleablood $\endgroup$ – salsabil.raisa Jan 31 at 4:39
4
$\begingroup$

Let $a$ be your number. Then note that $a + 1$ divided by $4, 5, 6 \text{ and } 7$ will give remainders of $0$ in all cases. Thus, the smallest positive $a + 1$ will be the smallest number which $4, 5, 6 \text{ and } 7$ all divide into. Since $6$ and $4$ each have a factor of $2$, you don't need to repeat this factor, giving it to be $4 \times 3 \times 5 \times 7 = 420$, giving that $a = 419$ works.

Note that, in general, $a = 420n - 1$ for any integer $n$.

$\endgroup$
  • $\begingroup$ Beautiful, elegant solution! Perfectly aligns with JMoravitz's comment on modular arithmetic, and adding the lcm to the mod $\endgroup$ – Christopher Marley Jan 31 at 4:16
  • $\begingroup$ @ChristopherMarley Thanks for the compliment. I tried to keep it quite simple based on my perception of the OP's limited math knowledge, such as the request to not using modular arithmetic. Similarly, I chose to not explicitly mention the lcm for the same reason. $\endgroup$ – John Omielan Jan 31 at 4:19
  • $\begingroup$ Thank you so much. The solution is a lot simpler than I have thought. :) $\endgroup$ – salsabil.raisa Jan 31 at 4:26
  • $\begingroup$ @salsabil.raisa You are welcome. Quite often there's some little trick with these sorts of problems that makes them fairly easy to solve. $\endgroup$ – John Omielan Jan 31 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.