How do I verify if $2^{35} \equiv 1 \pmod{71}$ is true or not?

Question

I need to know if $2^{35} \equiv 1\pmod{71}$ is true. I tried using Euler and Fermat little theorem and I got stuck. There is probably something trivial I'm not seeing so I appreciate any help, thanks.

Answer 1

Here's another way:

$$ 2^{36}\equiv 64^6 \equiv (-7)^6 \equiv (-343)^2 \equiv 12^2 \equiv 2 \pmod{71} \Rightarrow 2^{35} \equiv 1 \pmod{71} $$

Answer 2

$$2^{35} = 2^{10} \times 2^{10} \times 2^{10} \times 2^5 \\ = 1024 \times 1024 \times 1024 \times 32 \\ \equiv 30 \times 30 \times 30 \times 32 \equiv 1 \mod 71.$$

Answer 3

According to Euler's criterion, $2^{35}\equiv\left(\dfrac2{71}\right)\bmod71$.

Furthermore, $\left(\dfrac2{71}\right)=1$, because $71\equiv-1\bmod8$.

Answer 4

Since $71\equiv3$ mod $4$, $k$ is a quadratic residue if and only if $71-k$ is a nonresidue. In particular, $70=71-1$ and $35=71-36$ are nonresidues. But since $70=2\cdot35$, we can conclude that $2$ is a quadratic residue, i.e., $2\equiv a^2$ mod $71$ for some $a$, in which case $2^{35}\equiv a^{70}\equiv1$ mod $71$ by Fermat's little theorem.

Remark: This approach shows that $2$ is the square of something without explicitly finding what it's the square of. In fact, as Keith Bachman points out in comments, $2\equiv12^2$ mod $71$.