Congruence question and prime numbers

Question

Let $p$ be an odd prime number when $p-1=2^{s}\cdot t$, $s\in \mathbb{N}, t\in \mathbb{Z}$ and $t $ is odd. Need to prove that if $(a,p)=1$, then $a^{t}\equiv 1 \pmod{p}$ or $a^{2^{i}\cdot t}\equiv -1 \pmod{p}$, for $0\le i\le s-1$. In addition $a\in \mathbb{Z^{+}}$.

---

My attempt: suppose that $(a,p)=1$ and $p-1=2^{s}\cdot t$. Since $0\le i\le s-1$ then let $s=i+x$, for $x\in \mathbb{N}$. According to little's Fermat theorem, since $(a,p)=1$ we have that: $a^{p-1}\equiv 1 \pmod{p}$. Recall that $p-1=2^{s}\cdot t$ so by substitution - $a^{p-1}\equiv a^{2^{s}\cdot t}\equiv 1 \pmod{p}$. Now by substitution of $s=i+x$ we get: $a^{2^{i}\cdot 2^{x}\cdot t}\equiv (a^{2^{i}\cdot 2^{x}})^{t}\equiv (a^{2^{i}\cdot t})^{2^{x}}\equiv 1 \pmod{p}$. From here I don't know how to proceed, but I still didn't use the definition of t and p being odd prime numbers. Therefore I will be glad to get some help. Thanks!

Answer 1

Hint

If $\ a^{2^st}\equiv1\pmod{p}\ $, then $\ \left(a^{2^{s-1}t}-1\right)\left(a^{2^{s-1}t}+1\right)\equiv$$0\pmod{p}\ $, so either $\ a^{2^{s-1}t}\equiv1\pmod{p}\ $ or $\ a^{2^{s-1}t}\equiv-1\pmod{p}\ $. If the second alternative holds, you're home. Otherwise, now play the same game with $\ s-1\ $ in place of $\ s\ $.

Hint for another approach

Here's another approach which you might find easier. The multiplicative order $\ \sigma\ $ of $\ a\ $ mod $\ p\ $ must be a divisor of $\ p-1=2^st\ $—that is $\ \sigma=2^jv\ $, where $\ 0\le j\le s\ $ and $\ t=vw\ $ with $\ v\ $ and $\ w\ $ both odd. If $\ j=0\ $, what is $\ a^v\pmod{p}\ $? What then is $\ a^{vw}=a^t\pmod{p}\ $? If $\ j\ge1\ $ and $\ i=j-1\ $, what is $\ a^{2^iv}\pmod{p}\ $? What then is $\ a^{2^ivw}=a^{2^it}\pmod{p}\ $?