# Congruence Class of mod p where p is a prime number

If $$n =p$$ is a prime number and if $$[0]\neq[a]$$ is in $$J_p$$ , then there is an element $$[b]$$ in $$J_p$$ such that $$[a][b] = [1]$$. ($$J_p$$ being the set of congruence classes mod $$p$$)

This was a remark in the book Topics of Algebra by I.N. Herstein in the congruence modulo section of the topic Integers. He didn't prove it.

I tried to prove it but I have no clue as to how I'm supposed to approach this, all I could do is simplify this to : Prove, for all $$a there exists a $$b such that $$ab=np + 1$$ where $$p$$ is prime and $$n ( is any integer.

Could anyone show how this is true or maybe help me out with how to approach it.

You can use the existence of a Bézout identity: since $$[a]\neq[0]$$, $$p$$ does not divide $$a$$, in particular $$a$$ is prime to $$p$$ and there exist integers $$b$$, $$q$$ such that $$ab+pq=1$$, for the classes in $$J_p$$, this implies $$[a][b]+[p][q]=[1]$$, but since $$[p]=[0]$$, this yields $$[a][b]=[1]$$.

Let $$p$$ be prime and let $$a, b$$ be integers less than $$p$$. We know from Fermat’s little theorem that $$a^{p-1}=1 (mod p)$$

Thus, we have that $$b=a^{p-2} (mod p)$$ satisfies this congruence.

• But how do you know that $a^{p-2}< p$. Also i think you meant $b = a^{p-2}$. Apr 23, 2019 at 7:32
• You do not need $a^{p-2}\lt p$ to be true, as we are dealing with congruence classes. We have that $a^{p-2}=b+np$ as shown by the modular arithmetic for some integer $n$, so our least positive residue, ie less than p, is simply b. Apr 23, 2019 at 8:44
• Ah I see, thanks. Apr 23, 2019 at 9:39

If $$a=1$$ then the result is immediate, so suppose $$1.

Consider the first $$p$$ multiples of $$a$$, which are $$a, 2a, 3a, \dots, pa$$. Suppose two of these leave the same remainder modulo $$p$$ - say $$ma=na \mod p$$ with $$m>n$$. Then $$(m-n)a$$ is a multiple of $$p$$. But since $$1, this would give a factorization of $$p$$ which is not the trivial factorization $$1 \times p = p$$. Since $$p$$ is prime a non-trivial factorization does not exist. Therefore the first $$p$$ multiples of $$a$$ must all leave different remainders modulo $$p$$.

But there are only $$p$$ different remainders modulo $$p$$, so one of the multiples $$ka$$ with $$1 must leave remainder $$1$$ modulo $$p$$.