Proposition 4 in this paper. The proof they give is very brief, can someone explain it?
For $p$ a prime, $q=2p-1$, $b$ prime to $N=pq$, why does the following equivalence hold?
$b^{pq-1}\equiv 1 \mod pq \iff b^{p-1}\equiv 1 \mod q$
/edit: I understand now why $b^{pq-1}\equiv 1 \mod pq \iff \left(\frac qb\right)=\left(\frac bq\right)=1$ holds (thanks to N. S.!)
Now I want to show this happens in exactly half of the cases. It is known that $\left(\frac bq\right)=1$ for half of all $b=1,\ldots,q-1$. However, I need to consider $b=q-1,\ldots,N-1$ as well. How?
Since $p,q$ are primes we have by Euler Theorem $$b^{(p-1)(q-1)} \equiv 1 \pmod{pq}$$
Therefore $$b^{pq-1} \equiv b^{p+q-2} \pmod{pq}$$
This shows that $$b^{pq-1} \equiv 1 \pmod{pq} \Leftrightarrow b^{p+q-2} \equiv 1 \pmod{pq}$$
Now, modulo $p$ we have $$b^{p+q-2} \equiv b^{3p-3} \equiv 1 \pmod{p}$$ by Fermat Little Theorem.
Therefore, by the Chinese Remainder Theorem $$b^{pq-1} \equiv 1 \pmod{pq} \Leftrightarrow b^{p+q-2} \equiv 1 \pmod{q}$$
Now use the fact that $b^{q-1} \equiv 1 \pmod{q}$ and you are done.
Addedd For the new question, just use the fact that if $b >q$ then $b=cq+r$ and $$b \equiv r \pmod{q}$$
Thus $q+1,..,2q-1$ are simply $1,.., q-1$, $\pmod{q}$ and so on. Thus the numbers $1,2,..,q-1,q+1,.., N-1$ modulo $q$ are simply the numbers $1,2,..,q-1$, each repeated the same number of times.