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


But try the problem first…

Answer:only $0$,$\pm1$

Source
Suggested Reading

TIFR 2010|PART B |PROBLEM 12

ELEMENTARY NUMBER THEORY DAVID M.BURTON

Try with Hints


First hint

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

Second Hint

Now there can be two cases

casei) $19\mid n$

caseii) n is not divisible by 19

Final Step

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$

Subscribe to Cheenta at Youtube