A question about a proof of Proth's Theorem

Question

This theorem is

The number $N=2^n\cdot k+1$ with $k<2^n$ is prime if and only if there exists $a$ with $a^{(N-1)/2}\equiv -1\mod N$

This proof is

$\Longrightarrow$ : If $N$ is prime, let $a$ be a primitive root of $N$.

Fermat's little theorem gives $a^{N-1}\equiv 1\mod N$ , hence $a^{(N-1)/2}\equiv \pm1\mod N$.

But since $a$ is a primitive root , we cannot have $a^{(N-1)/2}\equiv 1\mod N$

$\Longleftarrow$ : Now suppose, there exists $a$ with $a^{(N-1)/2}\equiv -1\mod N$.

Let $s$ be the order of $a$ modulo $N$, in other words the smallest positive integer with $a^s\equiv 1\mod N$.

Since $a^{N-1}\equiv 1\mod N$ , we have $s\mid N-1$

If we write $s=2^m\cdot p$ with odd $p$ , we cannot have $m<n$ because then we would have $a^{(N-1)/2}\equiv 1\mod N$ because $s$ would divide $(N-1)/2$.

Hence $s$ is at least $2^n$.

If $q$ is a prime factor of $N$, we have $a^{q-1}\equiv 1\mod q$ because $a$ and $q$ must be coprime, and $s$ must be the order of $a$ modulo $q$, otherwise $s$ would not be the order of $a$ modulo $N$.

Hence, we have $s|q-1$. So, $q>s$.

Since $s$ is at least $2^n$ and $k<2^n$, we can conclude that every prime factor $q$ of $N$ must exceed $\sqrt{N}$ and this implies that $N$ must be prime.

I'm trying to understand this step:

If $q$ is a prime factor of $N$, we have $a^{q-1}\equiv 1\mod q$ because $a$ and $q$ must be coprime, and $s$ must be the order of $a$ modulo $q$, otherwise $s$ would not be the order of $a$ modulo $N$.

I know that $a^{q-1}\equiv 1\pmod q$ is because "$a$ and $q$ are coprime" (since $a$ and $N$ are coprime).

But I don't know how "$s$ must be the order of $a$ modulo $q$" is deduced from "otherwise $s$ would not be the order of $a$ modulo $N$".

I think
$a^s\equiv1\pmod N⇒a^s\equiv1\pmod q⇒s$ is a multiple of the order of $a$ modulo $q$
which doesn't imply that $s$ is equal to the order of $a$ modulo $q$.

E.g. $5$ is a prime factor of $35$.
The order of $2$ modulo $35$ is $12$,
the order of $2$ modulo $5$ is $4$, and $12\ne4$.

Answer 1

Here's how I would rewrite the part of the referenced proof which you question . . .

Assume $N=2^n\cdot k+1$ with $k<2^n$.

We can assume $k$ is odd since that would only increase $n$ and decrease $k$.

Now suppose $a$ is such that $a^{(N-1)/2}\equiv -1\;(\text{mod}\;N)$.

Let $q$ be a prime factor of $N$, and let $s$ be the order of $a$ mod $q$.

Then $a^{q-1}\equiv 1\;(\text{mod}\;q)$, hence $s{\,\mid\,}(q-1)$.

But from $$ \left\lbrace \begin{align*} a^{(N-1)/2}&\equiv -1\;(\text{mod}\;N)\\[4pt] a^{N-1}&\equiv 1\;(\text{mod}\;N)\\[4pt] \end{align*} \right. $$ we get $$ \left\lbrace \begin{align*} a^{(N-1)/2}&\equiv -1\;(\text{mod}\;q)\\[4pt] a^{N-1}&\equiv 1\;(\text{mod}\;q)\\[4pt] \end{align*} \right. $$ hence $s{\,\mid\,}(N-1)$ but $s{\,\not\mid\,}\bigl((N-1)/2\bigr)$

It follows that $2^n{\,\mid\,}s$.

To explain the above claim, write $s=2^mj$, where $j$ is odd.

Then from $s{\,\mid\,}(N-1)$ we get \begin{align*} & (2^mj){\,\mid\,}(2^nk) \\[4pt] \implies\;& 2^m{\,\mid\,}2^n \;\text{and}\; j{\,\mid\,}k && \bigl(\, \text{since $k$ is odd} \,\bigr) \qquad\qquad\;\;\;\; \\[4pt] \implies\;& m\le n \\[4pt] \end{align*} and from $s{\,\not\mid\,}\bigl((N-1)/2\bigr)$ we get \begin{align*} & (2^mj){\,\not\mid\,}(2^{n-1}k) && \bigl(\, \text{since $(N-1)/2=2^{n-1}k$} \,\bigr) \\[4pt] \implies\;& 2^m{\,\not\mid\,}2^{n-1} && \bigl(\, \text{since $j{\,\mid\,}k$} \,\bigr) \\[4pt] \implies\;& m > n-1 \\[4pt] \implies\;& m\ge n \\[4pt] \end{align*} Thus $m=n$, so $2^n{\,\mid\,}s$, as claimed.

Then $\sqrt{N} < 2^n\le s\le(q-1) < q$.