Reminder of equation

Question

I have a simple(maybe too simple) question - how to find the reminder of equation? For example:

$(85^{74}+17^{95})^{15} \equiv \ ? \ (mod\ 13)$

I know that it is something simple, but I couldn't get it :( .

I will be very helpful if someone got some time and explain it.

Answer 1

You can split it into pieces.

For example, working modulo $13$, note that $85\equiv 7$. Also $17\equiv 4$. So we are now looking at $$(7^{74}+4^{95})^{15}$$

Next we note that if $(n,13)=1$ Fermat tells us that $n^{12}\equiv 1$, so we can reduce the exponents by arbitrary multiples of $12$. This gives us $$(7^2+4^{-1})^3$$

Now we note that $4\cdot 10=40\equiv 1$ so that $4^{-1}$ can be replaced by $10$ to give $$59^3\equiv 7^3$$

Then it is by hand. $7^3=343$ is a fact I know. $343=26\cdot 13+5$

Answer 2

Doing arithmetic modulo $\;13\;$ all the way:

$$\left(85^{74}+17^{95}\right)^{15}=\left(7^{74}+4^{95}\right)^{15}$$

But

$$7^2=10=-3\;,\;\;7^4=(-3)^2=9\;,\;\;7^5=9\cdot7=11=-2\;,\;\;7^6=7\cdot(-2)=-1\implies$$

$$7^{74}=\left(7^6\right)^{12}\cdot7^2=10$$

Likewise

$$4^3=64=-1\implies 4^{95}=\left(4^3\right)^{31}\cdot4^2=-16=10$$

Thus

$$\left(7^{74}+4^{95}\right)^{15}=7^{15}=7^{13}\cdot7^2\stackrel{\text{Fermat's Little Th.}}=7\cdot10=5$$