0
$\begingroup$

I am answering a exercise consisting of three parts.

Here are the exercises:

Suppose $p$ is an odd prime.

1) Show that if $a \in \mathbb{Z}$ and $p$ doesn't divide $a$ then there exists unique $a'$ (unique here means unique modulo $p$) such that $aa' \equiv 1 \mod p$.

2) Find the values of $a$ for which $a \equiv a' \mod p$.

3) Show $(p-1)! \equiv -1 \mod p$.

I have done 1) by saying since $p$ doesn't divide $a$ then the only common factor must be $1$ since $p$ is prime so the $\text{hcf}$ is $1$ and so there is only one (that is unique) solution to the equation $ax \equiv 1 \mod p$ call this solution $a'$ and we are done.

For 2) and 3) I am utterly lost.

Could anyone help?

Thanks.

$\endgroup$
8
  • $\begingroup$ The problem say "$p$ doesn't divide $a$", but your solution to 1) says "$a$ doesn't divide $p$". Since $p$ is prime most values of $a$ won't divide $p$, but $a=1$ will divide $p$. $\endgroup$ – Χpẘ Mar 30 '17 at 21:17
  • $\begingroup$ Perhaps you mean to be asking about $\Bbb Z_p$ instead of $\Bbb Z$. What will be true is that given $a\in \Bbb Z_p$ with $a\neq 0$ there is a unique $a'\in \Bbb Z_p$ such that $aa'\equiv 1\pmod{p}$... I.e. you are being asked to show that multiplicative inverses are unique in the ring $(\Bbb Z_p,+,\times)$ $\endgroup$ – JMoravitz Mar 30 '17 at 21:21
  • $\begingroup$ Yes I mean that they are unique modulo $p$. And my answer contained a typo which has since been fixed. Any help on parts 2/3? $\endgroup$ – Ryan S Mar 30 '17 at 21:22
  • $\begingroup$ For 1) prove existence via euclidean division algorithm and that $p$ is coprime to $a$. For uniqueness, suppose you have $aa'\equiv ab' \equiv 1\pmod{p}$ with $a'\not\equiv b'\pmod{p}$ and left-multiply by $a'$, giving $a'\equiv b'\pmod{p}$ a contradiction. For 2) notice how $1^2=1$ and $(-1)^2=1$. Are there any others? For 3), use what you learned in 2) $\endgroup$ – JMoravitz Mar 30 '17 at 21:25
  • $\begingroup$ I get 1) but I don't understand what you are hinting at in 2) sorry. $\endgroup$ – Ryan S Mar 30 '17 at 21:27
1
$\begingroup$

For 2), $a\equiv a' \mod p$ means $a^2=1$. Now the congruence classes $\mathbf Z/p\mathbf Z$ are a field, which implies the quadatic equation $a^2-1=0$ has at most two roots. And indeed it has: $1$ and $-1$ˆ.

For $3)$ (which is known as Wilson's theorem), note that each congruence class $a$, except the classes of $1$ and $p-1\equiv 1$, which are their own inverse, is associated with another class $a'$ such that $aa'\equiv 1$. So $$(p-1)!= 1\cdot2\cdots\cdot (p-2)(p-1)\equiv 1\cdot(-1)\cdot\!\prod_{2\le a\le p-2}\!a\equiv 1\cdot(-1) \cdot1^{\tfrac{p-3}2}=-1. $$

$\endgroup$

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.