Modular Arithmetic Involving Remainders

79 Views Asked by At

Using modular arithmetic, solve the following:

Find the remainder of $(2014^{2015} \cdot 2016^{2017}) + 2018^{2019}$ when it is divided by 13.

I have no idea where to start. I've tried putting this in (mod 13) but I'm not sure where to start or even finish.

Any help would be appreciated.

1

There are 1 best solutions below

3
On

You need the little Fermat's theorem (or very much patience...). This theorem guarantee that, in particular, $x^{13}\equiv x\pmod {13}$. Or more generally, $$x^{n+12k}\equiv x^n\pmod {13}$$ for any integer $k$.

Now, $2014\equiv -1\pmod{13}$, $2016\equiv 1\pmod {13}$ and $2018\equiv 3\pmod {13}$, so

$$2104^{2015}\cdot2016^{2017}+2018^{2019}\equiv -1\cdot 1+3^{168\cdot12+3}\equiv -1+3^3\equiv 0\pmod{13}$$