From XGCD to Multiplicative Inverse

Question 1

By XGCD,we can solve the equation:$xa+yp=1$,where $a$ and $p$ are relative prime integers,and $x$ is $a$'s inverse modulus $p$.

If $x'$ is another inverse of $a$ modulus $p$,that will satisfy $x'a+y'p=1$.So we get: $(x'-x)a+(y'-y)p=0$.

Hence,$(x'-x)a \equiv0\pmod{p}$
-> $x'-x=kp$
-> $x'=x+kp$.

That is,$x'$ mod $p$ equal to $x$ instead of $x'$.

So,$x$ is the unique inverse of $a$ modulus $p$.

Question 3 $(p-1)! \equiv-1\pmod{p}$

From Question 1 we know that $\forall a \in [1,...,p-1]$ has a unique inverse $a^{-1}$ and $a^{-1}$ $\in [1,...,p-1]$.

And from Question 2,we know that only $1$ and $p-1$ has a inverse which is itself.

In other words,except for $1$ and $p-1$,there exists many pairs of number that they inverse each other modulus p.

So:
$(p-1)! \mod p = ((p-1)\mod{p} )\cdot\begin{matrix}\underbrace{ 1 \cdot1...\cdot1}\\ \frac{p-3}{2}\end{matrix}\ \cdot (1\mod{p})$ = $(p-1) \mod p$ = -1.

QED.

From $a^2 \equiv 1\pmod{p}$ to $a^2 \equiv 1\pmod{n}$

Conjecture:
1.If $n$ has x distincted prime factors and $n$ is odd,then $a^2 \equiv 1\pmod{n}$ has $2^x$ solutions(n>1).

2.If $n$ has x distincted prime factors and $n$ is even,then the equation has $2^{x-1}$ solutions.

3.If $n$ isn't a prime and $n$ is the power of 2,then the equation has 4 solutions.

Congruent Equation

Solve the following equation:$ax \equiv b\pmod{n}$,where $a$ and $n$ are not relative prime.
Let $d = gcd(a,n)$.

• two cases to consider:

1.when will the congruence has no solution:
If $d$ can't divide $b$,I think the equation is unsolvable.

2.If the congruence has solutions,how many incongruent solutions does it have?
I wonder if zero is a legal solution.If it is,then there will be $n/b-1$ incongruent solutions.

So,If we can solve this congruence,that means $b=kd$ where $k$ is an integer.

By XGCD,we can solve $ax+ny=d$,then we get $akx+nky=kd=b$

The solution of the congruence is $kx$.