Select Page

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

## Problem on Natural Numbers | TIFR 201O| PART B | PROBLEM 4

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$

### Key Concepts

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

TIFR 2010|PART B |PROBLEM 12

ELEMENTARY NUMBER THEORY DAVID M.BURTON

## Try with Hints

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.