What is the remainder when $15^{40}$ divided by $1309$? I know that $$ 15 \equiv 1\pmod{7}, N \equiv 1\pmod{7},$$ but cannot proceed further.

Note that $1309=7 \cdot 11 \cdot 17$. Let $N=15^{40}$.
Since $15 \equiv 1\pmod{7}$, $N \equiv 1\pmod{7}$.
Since $15^{10} \equiv 1\pmod{11}$, $N=\big(15^{10}\big)^4 \equiv 1\pmod{11}$.
Since $15 \equiv -2\pmod{17}$, $15^4 \equiv (-2)^4 \equiv -1\pmod{17}$ and $N=\big(15^4\big)^{10} \equiv (-1)^{10}=1\pmod{17}$.
Therefore $N-1$ is divisible by $7$, $11$, and $17$, and hence by $1309$.
The remainder is $1$.
