Given the following method to decide whether a number $m$ is prime or not:
Choose a random number $1<a<m-1$, and check whether $a^{m-1} = 1 \mod m$. If its equal, return true, otherwise - false.
Now obviously this method isn't going to work always, but what I am trying to do is to find a lower bound to the probability that, given a simple number $m=p\cdot q$ where $p < q$ are two (different) primes, our above method will give us "true".
What I had in my mind is like that - I was given the hint that there exists an $1<a_0<p-1$ such that for each $0<x<p-1$ we have $a_0^x\neq 1 \mod p$. So what I did is like that: denote $w=q^{-1} \mod p$ and $c=1+(a_0 -1)\cdot w \cdot q$. So now I know that $c=a_0 \mod p$ (simply by definition). But I got a bit unsure as for calculating $c^{m-1} \mod m$? I think that its $=1 \mod m$, but not sure on that. And besides, I'm not exactly sure on how this hint assists me in finding a lower bound to the probability that we'll return true?
Or perhaps there's an easier way to see such a bound?
We need the following sub-theorem: if there exists such an $a_0$ so that $a_0^{m-1} \not\equiv 1 \mod m$ (where $\gcd(a_0,m) = 1$, ofcourse), then for at least half the $a$'s in $\mathbb{Z}_m$ we know that $a^{m-1}\not\equiv 1 \mod m$.
Back to your main proof/question - show that $a_0^{m-1} \not\equiv 1 \mod m$ (which is not too hard to do using Euler's theorem).
Now we can use the sub-theorem. Thus, knowing that if we randomly choose an $a\in\mathbb{Z}_m$ we have a probability $\geq \frac{1}{2}$ that $a^{m-1} \not\equiv 1 \mod m$, which will show to us that $m$ is not prime.