1

Can anyone help me with this? Thank you very much!

Problem: Find two integers between 1 and 100 such that for each: a) if you divide by 4, the remainder is 3; b) if you divide by 3, the remainder is 1; and c) if you divide by 5, the remainder is 1.

Here is what I have done: assume $x$ is the number, then I have equations as following. I don't know how to find $x$ from here.

$$x\equiv3\pmod{4}$$ $$x\equiv1\pmod{3}$$ $$x\equiv1\pmod{5}$$

learning
  • 1,749

2 Answers2

3

First, we can combine the last two equations into: $$x \equiv 1 \pmod{\text{lcm}(3,5)} \implies x \equiv 1 \pmod{15}$$ We can do this because the last two equations have the same remainder, meaning $x$ has the same remainder when divided by their LCM.

Now, we can use the Chinese Remainder Theorem. We have the following: $$x \equiv 3 \pmod 4 \implies x=4t+3 \text{ for some } t \in \Bbb{Z}$$ Now, substitute into the second equation: $$x \equiv 1 \pmod {15} \implies 4t+3 \equiv 1 \pmod {15} \implies 4t \equiv -2 \pmod {15}$$ Now, find the modular inverse of $4 \pmod{15}$, which is $4$, so multiply both sides by $4$ to get: $$t \equiv -8 \equiv 7 \pmod{15} \implies t=15s+7 \text{ for some } s \in \Bbb{Z}$$ Thus, we have: $$x=4t+3=4(15s+7)+3=60s+31 \text{ for some } s \in \Bbb{Z}$$ Now, test different values of $s$: $$s=0 \implies x=31$$ $$s=1 \implies x=91$$

Noble Mushtak
  • 18,402
  • 28
  • 44
1

According to given equations, it can be written as $x=4a+3=3b+1=5c+1$ where $a,b,c$ are non negative integers. Now questions is to find common terms between $3$ sequences $A_n,B_n,C_n$ such that $A_n=4n+3,B_n=3n+1,C_n=5n+1$ which can be found out easily as all the sequences are AP. Now common terms between $B_n$ and $C_n$ is $D_n=15n+1$. So now find common terms between $A_n$ & $D_n$ and $0\le n\le6$ which can be easily seen that common terms are 31 and 91.

Hope this will be helpful !!!

Vineet Mangal
  • 943