In a proof in my lecture notes on number theory for Euler's criterion, my lecturer asserts that if $a$ is a quadratic non residue then $$\forall c\in\{1,...,p-1\}\, \exists c'\in\{1,....,p-1\}\text{ s.t. }cc'\equiv a \pmod{p} \text{ with } c'\neq c.$$
Why is this so ?
$$\mbox{**A Solution Using Modular Arithmetic**}$$
Assuming $p$ is a prime number, we can say that $\gcd(c,p)=1$ and so there exists a multiplicative inverse of $c$ in the ring $\mathbb{Z}/p\mathbb{Z}$ say $c''$. Then define $$c'=ac''$$Therefore, it is easy to see that $c'\neq 0$ in the ring $\mathbb{Z}/p\mathbb{Z}$ (because $p\nmid a$). Therefore, $$cc'\equiv c\cdot (ac'')\equiv(cc'')\cdot a\equiv a\pmod{p}$$which completes the proof.
Note: $c\neq c'$, else $$cc'\equiv c^2\equiv a\pmod{p}$$which contradicts that $a$ is a quadratic non residue.
$$\mbox{**A Solution Using Division Algorithm**}$$ Consider a number $c$ such that $\gcd(c,p)=1$. Therefore, there exists integers $c''$ and $k$ such that $$cc''-pk=1$$by bezout's identity . Therefore, $$pk=cc''-1 \implies pka=acc''-a$$where $a$ is a QNR. It is easy to note that $\gcd(c'',n)=1\implies ac''\in\{1,2,\ldots,p-1\}$. We consider $c'=ac''$ and hence,$$p\mid cc'-a\implies cc'\equiv a\pmod{p}$$Since $a$ is a NQR, $c\ne c'$ which completes the proof.