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$?

  • 2
    $\begingroup$ $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.$ $\endgroup$ – awllower Jul 6 '16 at 8:18
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 6 '16 at 8:21
  • $\begingroup$ @joriki: I got it by using the fermat's little theorem. Thanks! $\endgroup$ – TheMathNoob Jul 6 '16 at 8:55
  • $\begingroup$ Using Fermat's Theorem may not be the best way, since this is one of the standard ways to prove Fermat's Theorem. $\endgroup$ – 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$.

The second question has already been answered by awllower in a comment.

  • $\begingroup$ Hello joriki, I haven't gone over Fermat's little theorem yet. $\endgroup$ – TheMathNoob Jul 6 '16 at 8:23
  • $\begingroup$ @TheMathNoob: Then you should add context to the question and state what results you're willing to use in the proof. $\endgroup$ – joriki Jul 6 '16 at 8:25
  • $\begingroup$ @TheMathNoob Your other questions are on quadratic reciprocity, so I think it's time to look at Fermat's little theorem now. $\endgroup$ – Dietrich Burde Jul 6 '16 at 8:26
  • $\begingroup$ Sure, so far I have been working on euler's criterion and wilson's theorem. I am just wondering if it can be shown that the latter holds by just using the basics of congruence and reduced residue system. $\endgroup$ – TheMathNoob Jul 6 '16 at 8:27
  • $\begingroup$ @TheMathNoob: OK, I'll delete my answer. I don't know what's part of "the basics of reduced residue system" for you. Anyway, these comments won't be visible to everyone once the answer is deleted; you should add the information to the question itself. $\endgroup$ – joriki Jul 6 '16 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.