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:-

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