If a^(N-1) (is not≡) 1 mod N for some a relatively prime to N, then it must hold for at least half the choices of a < N. 
Here, in the proof of the above lemma, I'm not able to understand why for every b less than N that passes the Fermat's test, there is a twin (a.b) that fails the Fermat's test.
 A: Let $C$ be the set of those $c\in \{1,..., N-1\}$ for which $\gcd (c,N)=1.$ Let B be the set of those $b\in C$ for which $b^{N-1}\equiv 1\pmod N.$ Let $A =C$ \ $B.$ Assume $a\in A.$
For $b\in B$ let $f(b)\in \{0,1,...,N-1\}$ such that $ab\equiv f(b) \pmod N.$
Then $\gcd (f(b),N)=\gcd (ab,N)=1$ because $\gcd (a,N)=\gcd(b,N)=1.$ And $f(b)\ne 0$ because $$f(b)=0\implies N|ab \implies N|b \text {... (because } a\ne 0 \text { and } \gcd (a,N)=1)....$$ $$\implies b=0 \text {... (because } |b|<N) ...$$ $$\implies b\not \in B \text {... (by def'n of } B). $$ $\bullet \;$ So $f(b)\in C.$ And  $f(b)^{N-1}\equiv a^{N-1}\not \equiv 1 \pmod N$ so $f(b)\in A.$ 
For $b,b'\in B$ we have $$f(b)=f(b')\iff N|a(b-b') \iff N|(b-b') \text {...  (because } a\ne 0 \text { and } \gcd (a,N)=1)...  $$ $$\iff b-b'=0 \text {... (because } |b-b'|<N).$$
$\bullet \;$ So $f$ is a $1$-to-$1$ function from $B$ into $A.$ So $A$ has at least as many members as $B$ does. 
Since $A\cap B=\emptyset$ and $A\cup B=C,$ and $A$ has at least as many members as $B$ does, therefore at least half of the members of $C$ belong to $A.$
