How do I verify if $2^{35} \equiv 1 \pmod{71}$ is true or not? 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.
 A: $$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.$$
A: According to Euler's criterion, $2^{35}\equiv\left(\dfrac2{71}\right)\bmod71$.
Furthermore, $\left(\dfrac2{71}\right)=1$, because $71\equiv-1\bmod8$.
A: 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$.
A: 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}
$$
A: Using only 'ground floor' modular arithmetic theory, you can build a bottom-up presentation of exponent relations of the $\text{modulo-}71$ structure to answer this question.
To get things moving, you solve $2x = 1 \pmod{71}$ and find that $\large 2^{-1} = 2^2 \cdot 3^2 \pmod{71}$.
So,
$\quad 2^{35} \equiv 1 \pmod{71} \; \text{ iff}$
$\quad 2^{34} \equiv 2^2 \cdot 3^2 \pmod{71} \; \text{ iff}$
$\quad 2^{32} \equiv  3^2 \pmod{71}$
Observing the exponent pattern (down $3$, up $2$), and since $3^4 = 2 \cdot 5 \pmod{71}$, we take $8$ 'pivot' steps and continue the calculations,
$\quad 2^{35} \equiv 1 \pmod{71} \; \text{ iff}$
$\quad 2^{11} \equiv 3^{16} \pmod{71}\; \text{ iff}$
$\quad 2^{11} \equiv 2^{4}\cdot 5^{4} \pmod{71}\; \text{ iff}$
$\quad 2^{7} \equiv 5^4 \pmod{71}\; \text{ iff}$
$\quad 128 \equiv 625 \pmod{71}\; \text{ iff}$
$\quad 128 \equiv -85 \pmod{71}\; \text{ iff}$
$\quad 213 \equiv 0 \pmod{71}$
We have verified that the statement $2^{35} \equiv 1 \pmod{71}$ is true.
