Fermat's Little Theorem has a very nice proof ...
Take $\displaystyle p$ is prime and $\displaystyle x>0$. (You have already stated that $\displaystyle p$ does not divide $\displaystyle x$).
You can easily prove that $\displaystyle \left\{x,2x,...,(p-1)x\right\}=\left\{1,2,...,p-1\right\}$ (a basic proof by contradiction should do the trick).
Hence it must be the case that $\displaystyle x*2x*...*(p-1)x\equiv_{p}1*2*...*(p-1)$.
You can then collect the $\displaystyle x$ terms and observe that $\displaystyle x^{p-1}(1*2*...*(p-1)\equiv_{p}1*2*...*(p-1)$.
From this it follows that $\displaystyle x^{p-1}\equiv_{p}1$ as required
Hope that helps
Paul
Say that $\displaystyle \gcd (x,n)=1$ and $\displaystyle n=mp$.
If $\displaystyle x^{n-1}\equiv 1(\bmod p)$ then it means $\displaystyle x^{mp-1}\equiv 1(\bmod p)$ thus $\displaystyle x^{m-1}\equiv 1(\bmod p)$.
If $\displaystyle x^{m-1}\equiv 1(\bmod p)$ then $\displaystyle \left ( x^{m-1} \right)^p \equiv 1(\bmod p)$ so $\displaystyle x^{mp -p}\equiv 1(\bmod p)$ thus $\displaystyle x^{n - 1}\equiv(\bmod p)$.
We never used the condition $\displaystyle \gcd( m,p)=1$ anywhere. We do not need it. Generalize this to several primes.