 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

But try the problem first…

Answer:only $0$,$\pm1$

Source

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$