# Question about reduced residue system

Let $1,2,.......,p-1$ be a reduced residue system mod $p$ where $p$ is a prime number. If $\gcd\left(k,p\right)=1$ for an integer $k$ then we can say $k,2k,\dots,k(p-1)$ is also a reduced residue system mod $p$. My question is why the following holds

$$1*2*\dots*p-1 \equiv k*2k*....*k(p-1)(\mod\text{ } p)$$

My second question is if $$xt \equiv x (\mod\text{ } p)$$ where $x$ and $t$ are integers and the $\gcd(x,p)=1$, why can we cancel the $x$?

• $xt\equiv x\pmod p$ means $p$ divides $xt-x=x(t-1)$ while $p$ does not divide $x,$ so $p$ divides $t-1,$ i.e. $t\equiv1\pmod p.$ – awllower Jul 6 '16 at 8:18
• Since $k, 2k, \dots, k(p-1)$ form a reduced system modulo $p$, they are, in some order, congruent to $1,2,\dots,p-1$, so the two products are congruent. – André Nicolas Jul 6 '16 at 8:21
• @joriki: I got it by using the fermat's little theorem. Thanks! – TheMathNoob Jul 6 '16 at 8:55
• Using Fermat's Theorem may not be the best way, since this is one of the standard ways to prove Fermat's Theorem. – André Nicolas Jul 7 '16 at 3:29

You've multiplied by $k^{p-1}$, which by Fermat's little theorem is $1\bmod p$.