divisibility of big powers of 71 Since
                  $$ 71 \equiv7\equiv-1 \pmod 8 $$
$\implies71^2 \equiv 1 \pmod 8$
$\implies $ any  power of $71$ would leave either $1$ or $-1$ mod $8$.
Is this logic ok ?

You are absolutelly right. It's good to understand and always keep in mind the basic rules of modular arythmetic, so that you never have doubts about your reasonings. For instance, if:
$$a \equiv b \pmod k$$
$$c \equiv d \pmod k$$
Then 
$$ac \equiv bd \pmod k$$
And, as a consequence (set $a=c$, $b=d$ and apply the above equation recursively as many times as needed), for any integer $m$,
$$a^m = b^m$$
You are just applying this property to the case $a=71$, $b=-1$
On a sidenote it's also true that:
$$a+c \equiv b+d \pmod k$$
But, for instance:
$$2^1 \not\equiv 2^5 \mod 4$$
EXTRA: Elementary proof for that $a \equiv b \pmod{k}$ and $c \equiv d \pmod{k}$ imply $ac \equiv bd \pmod{k}$:
Let $a$ and $b$ be mod-$k$ congruent. Let also $c$ and $d$ de mod-$k$ congruent. Then 
$$a=wk+r_1$$
$$b=xk+r_1$$
$$c=yk+r_2$$
$$d=zk+r_2$$ 
For some integers $w,x,y,z$ and $r_1, r_2 \in \{0,1,...,k-1\}$. Now:
$$ac=wyk^2 + r_1yk + r_2wk + r_1 r_2 = (wyk+r_1y+r_2w)k + r_1 r_2$$
$$bd=xzk^2 + r_1zk + r_2xk + r_1 r_2 = (xzk+r_1z+r_2x)k + r_1 r_2$$
Long story short:
$$ac=sk+r_1 r_2$$
$$bd=tk+r_1 r_2$$
For some integers $s,t$ that we don't even care about. The point is that the remainder after a division by $k$ is in both cases $r_1 r_2$
