A condition that implies two numbers to be coprime?

Question

Consider the natural number $n=2^r\cdot s+1$, where $s$ is odd and suppose $a\in \mathbb N$ with $1<a<n$ is such that: $\exists j\in \mathbb N: j<r \wedge a^{2^j\cdot s}\equiv -1 \pmod n$.

Does this implies that $\gcd(a,n)=1$?

Answer 1

A power of $a$ is congruent to $-1\pmod n,$ which is prime to $n.$ I think this is enough for $a$ to be prime to $n,$ as every common divisor of $a$ and $n$ must divide $-1.$
Hope this helps.

Answer 2

$a^k \equiv - 1 \mod n$ is impossible unless $\gcd(a,n) = 1$. (Because $a^k - mn = -1 \implies \gcd(a,n)[\gcd(a,n)^{k-1}\frac{a}{\gcd(a,n)}^{k} - m\frac{n}{\gcd(a,n)}] = -1\implies \gcd(a,n) = 1$).

So this is actually simpler than you imply.