If one considers any number not divisible by $p$ and multiply it with each of the numbers $1,2,3\cdots\cdots p-1$, what happens? If one considers any number not divisible by $p$ and multiply it with each of the numbers $1,2,3\cdots\cdots p-1$, in turn one will get $p−1$ different numbers modulo p. How can we prove this? 
Note: p is prime here
I googled it, but not finding required proof.
 A: Let $x$ not be a multiple of $p$, and assume that $a$ and $b$ are such that $xa\equiv xb\pmod{p}$. Then $p\mid xa-xb = x(a-b)$. Since $p$ does not divide $x$ and is prime, then $p\mid a-b$, hence $a\equiv b\pmod{p}$.
By contrapositive, if $a\not\equiv b\pmod{p}$, then $xa\not\equiv xb\pmod{p}$. 
A: This answer is only for beginners like me, after reading this anybody can understand why this is true.
Here we assumed two different numbers $a,b$ where $0\le a<p$ and $0\le b<p$ and assumed $xa≡xb \mod n$. So in the last if we can prove $a=b$, then we are done.
If $xa≡xb \mod n$, then $x(a−b)\equiv 0 \mod n$. As $x$ is not divisible by $p$, then it means $(a−b)$ has to be divisible by $p$. Now as $0\le a<p$ and $0\le b<p$, so $−p<a−b<p$, so only number in this range which is divisible by $p$ is $0$, so it means $a−b$ has to be zero in order to be divisible by $p$, it means $a=b$
A: Euclids lemma..... If $p$ is prime and $p|MN$ then $p|M$ or $p|N$.
Proof by contrapositive..... If we can prove $ka\equiv kb\pmod p;a,b\in 1,...,p-1 \implies a=b$ that is enough to prove if $a\ne b;a,b\in 1,...,p-1\implies ka \not \equiv kb \pmod p$.....
Definition .... $a \equiv b \pmod p$ means by definition $p\mid a-b$....
====
Suppose $p \not \mid k$.  But suppose $ka \equiv kb\pmod p$.
Then by definition $p|ka-kb = k(a-b)$.
By Euclid's lemma that means $p|k$ or $p|a-b$.  But we are given the $p\not \mid k$ so $p|a-b$.
Which by definition means $a\equiv b\pmod p$.
.....
If on the other hand $a \not \equiv b \pmod p$ it would be impossible for $ak \equiv bk$
So if $a \not \equiv b \pmod p$ then $ak \not \equiv bk \pmod p$ for any $k$ not divisible by $p$.
And as the different values of $1,...,p-1$ are in different classes (why?) then the different values of $k, 2k,....,k(p-1)$ will be in different classes.
......
Okay.... a direct proof.
Let $a,b \in 1,...,p-1$ and $a \ne b$ and $p\not \mid k$.
First notice that the multiples of $p$ are $...., -3p, -2p,-p,0,p,2p,3p.....$ and if we have $-p < a-b < p$ and $a-b \ne 0$ then $p$ can not divide $a-b$.
And that is the case we have.  $a\ne b$ so $a-b \ne 0$  And $a < p$ and $b > 0$ so $a-b < p$.  And $a>0$ and $p <p$ so $a-b > -p$.
So we know $p\not \mid a-b$.
And we know $p\not \mid k$.
So, as $p$ is prime $p\not \mid k(a-b)$....( Hmm... okay, that is the converse of Euclid's lemma--  If $p|MN$ then $p|M$ or $p|N$ so if $p\not \mid M$ and $p\not \mid N$ then $p \not \mid MN$--  so this prove isn't entirely direct...)
So $p\not \mid k$ and $p\not \mid a-b$ so $p\not \mid k(a-b) = ka-kb$.
So $ka \not \equiv kb \pmod p$.
