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 \times 11 \times 17$. So $$15^{40} \equiv 1^{40} \equiv 1 \pmod {7}$$
Using $15 \equiv 1 \pmod {7}$. Then, $$15^{40} \equiv  \left(15^{10}\right)^4\equiv 1 \pmod {11}$$ 
And $$15^{40} \equiv (15+17 \times 2)^{40} \equiv 7^{80} \equiv \left(7^{16}\right)^5 \equiv 1 \pmod {17}$$
From Fermat's Little Theorem.  So $$15^{40} \equiv 1 \pmod {1309}$$
Using CRT. We are done. 
