Fermat's little theorem question

Question

I'm studying Number theory (in my spare time) and I need to prove a lemma in order to prove the exercise. The topic is Fermat's little theorem.

Well the lemma goes like this:

Let's say we have number N=pq where p,q are primes and $q<p$. According to a lemma, for every prime p, there exists some $a ∈ Z_p$ such that $a^x \not = 1$ mod $p$ for all $0<x<p-1$. The lemma I need to prove is the following one:

Assume we have the same $p,q,a$ from above, $q'=q^{-1}$ mod $p$, and $c=1+(a-1)q'q$.

I need to prove that:
$c^{N-1}$ mod $N \not = 1$.
I assumed that GCD$(c,N)=1$ if that helps (it's easy to prove).

Thank you!

Answer 1

Since $N=pq$ and $c^{N-1}\equiv 1\mod(q)$, it only needs prove $c^{N-1}\not\equiv 1 \mod(p)$.

As you know, $c^{N-1}\equiv a^{N-1}\mod(p)$.

Since $N-1=pq-1\equiv q-1 \mod(p-1)$, Fermat's theorem gives $$ c^{N-1}\equiv a^{N-1}\equiv a^{q-1} \mod(p) $$ But the assumption says $a^{q-1}\not\equiv 1\mod(p)$, we are done.