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$

Key Concepts

NUMBER THEORY

CONGRUENCE

CHINESE REMAINDER THEOREM

Check the Answer

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

Try with Hints

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.

Other useful links

Related Program

Subscribe to Cheenta at Youtube

Positive Integers Problem | TIFR B 201O | Problem 12

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

Positive Integers Problem | TIFR 201O | PART B | PROBLEM 12

If $n$ and $m$ are positive integers and $n^{19}=19m+r$ then the possible values for $r$ modulo $19$ are:-

  • only $0$
  • only $0$,$\pm1$
  • only $\pm1$
  • none of the above

Key Concepts

NUMBER THEORY

CONGRUENCE

FERMAT'S LITTLE THEOREM

Check the Answer

Answer:only $0$,$\pm1$

TIFR 2010|PART B |PROBLEM 12

ELEMENTARY NUMBER THEORY DAVID M.BURTON

Try with Hints

$r(mod 19)=(n^9-19m)(mod 19)=n^9(mod 19)-19m(mod 19)=n^9(mod 19)$ [because $19\mid19m$]

Now there can be two cases

casei) $19\mid n$

caseii) n is not divisible by 19

If $19\mid n$ then $19\mid n^9$ resulting in $n^9\equiv 0(mod 19)$

But if $n$ is not divisible by $19$ then according to Fermat's little theorem,

$n^{19-1}\equiv1(mod 19) =n^{18}\equiv 1(mod 19) = 19\mid n^{18}-1 =19\mid[n^9+1][n^9-1]$

i.e If $19\mid n^9+1$ then $n^9\equiv(-1)(mod 19) =r\equiv(-1)(mod 19)$

If $19\mid n^9-1$ then $n^9\equiv1(mod 19) = r\equiv1(mod 19)$

Thus $r(mod 19)=0$,$\pm1$

Other useful links

Related Program

Subscribe to Cheenta at Youtube