Problem on Natural Numbers | TIFR B 2010 | Problem 4

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$

NUMBER THEORY

CONGRUENCE

CHINESE REMAINDER THEOREM

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

TIFR 2010|PART B |PROBLEM 12

ELEMENTARY NUMBER THEORY DAVID M.BURTON

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$

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)$

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