# How to prove these linear congruence equations?

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.

• 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$. – Χpẘ Mar 30 '17 at 21:17
• 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)$ – JMoravitz Mar 30 '17 at 21:21
• 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? – Ryan S Mar 30 '17 at 21:22
• 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) – JMoravitz Mar 30 '17 at 21:25
• I get 1) but I don't understand what you are hinting at in 2) sorry. – Ryan S Mar 30 '17 at 21:27

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