INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More

Try this problem of TIFR GS-2010 using your concepts of number theory and congruence based on natural numbers.

Which of the following statements is false?

- There exists a natural number which when divided by $3$ leaves remainder $1$ and when divided by $4$ leaves remainder $0$
- There exists a natural number which when divided by $6$ leaves remainder $2$ and when divided by $9$ leaves remainder $1$
- There exists a natural number which when divided by $7$ leaves remainder $1$ and when divided by $11$ leaves remainder $3$
- There exists a natural number which when divided by $12$ leaves remainder $7$ and when divided by $8$ leaves remainder $3$

NUMBER THEORY

CONGRUENCE

CHINESE REMAINDER THEOREM

But try the problem first...

Answer:There exists a natural number which when divided by $6$ leaves remainder $2$ and when divided by $9$ leaves remainder $1$

Source

Suggested Reading

TIFR 2010|PART B |PROBLEM 12

ELEMENTARY NUMBER THEORY DAVID M.BURTON

First hint

Let us take the equations $x\equiv1(mod 3)$ and $x\equiv0(mod 4)$

Now we will apply Chinese remainder theorem to get the value of $x$

Second Hint

Since $3$,$4$ are relatively prime,gcd($3$,$4$)$=1$. Let $m=3\times4=12$

Then $M_1=4$,$M_2=3$.

Then gcd($M_1$,$3$)$=1$,gcd($M_2$,$4$)$=1$

Since gcd($4$,$3$)$=1$,therefore the linear congruence equation $4x\equiv1(mod 3)$ has a unique solution and $x\equiv1(mod 3)$ is the solution.

Since gcd($3$,$4$)$=1$,therefore the linear congruence equation $3x\equiv0(mod 4)$ has a solution and $x\equiv4(mod 4)$ is the solution.

Therefore,$x=1\times4\times1 +0\times3\times4=4$ is a solution.

The solution of the given system is $x\equiv4(mod 12)$

Final Step

So we have used the Chinese Remainder Theorem to check the statements, you may use it to check for other options.

- https://www.cheenta.com/triple-integral-iit-jam-2016-question-15/
- https://www.youtube.com/watch?v=oUyHFKVB9IY

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIAL
Google