show $2^{1194}+1$ is divisible by 65

Question

By assuming that it is divisible by $65$, we get $2^{1194}+1≡0$ mod $65$. Using the fact that if $p$ and $q$ are primes $x≡y\mod p$ and $x≡y\mod q \iff x≡y\mod pq$ we get: $2^{1194}≡12 \mod 13$ and $2^{1194}≡4\mod 5$, but what's next? By Euler's Theorem I know $2^{12}≡1\mod 13$, but the exponent $1194$ is too large to compute successive squaring, how can I bring it down?

Answer 1

$$2^6\equiv-1\pmod{13}$$

and $1194=1200-6=(200-1)6$

$$\implies2^{199\cdot6}=(2^6)^{199}\equiv(-1)^{199}\equiv-1$$

Similarly, $$2^{1994}=(2^2)^{997}\equiv(-1)^{997}\pmod5$$

Answer 2

Use that $$1194=6\cdot199$$ and that $199$ is odd.

Answer 3

$(x^{1194}+1)=(x^6+1)(x^{1188}-x^{1182}+...+x^{12}-x^6+1)$.

Now take $x=2$.

Answer 4

I don't think 1194 is large at all as you can do it in 11 steps, possibly less. But I digress. One way, is to note is that by that version of Euler's theorem ( technically Fermat's theorem) $2^p\equiv 2\pmod p$ and long divide the exponent by $p=13$ giving 91 remainder 11 and use basic exponent rules and repeating to go through:

$$2^{91}2^{11}\equiv 2^72^{11}\equiv 2^6\equiv 12\pmod {13}$$

Similarly by $q=5$ :

$$2^{238}2^4\equiv 2^{47}2^32^4\equiv 2^92^22^32^4\equiv 2^12^42^22^32^4\equiv 2^12^22^3\equiv 4\pmod 5$$

now you can combine using Chinese remainder theorem.