# Show that a^2 -1 = 0 mod p has only 2 solutions

• Oct 23rd 2011, 03:22 PM
restin84
Show that a^2 -1 = 0 mod p has only 2 solutions
I have an exercise for a course in Cryptography. One of the questions asks us to show that the equation a^2 -1 = 0 mod p has only 2 solutions.

we are told to consider the group Z sub p whose elements are {1,2,.....,p-1}.

I am having a hard time even finding a starting point for this problem. Can anyone give me some advice?
• Oct 23rd 2011, 05:52 PM
Prove It
Re: Show that a^2 -1 = 0 mod p has only 2 solutions
Quote:

Originally Posted by restin84
I have an exercise for a course in Cryptography. One of the questions asks us to show that the equation a^2 -1 = 0 mod p has only 2 solutions.

we are told to consider the group Z sub p whose elements are {1,2,.....,p-1}.

I am having a hard time even finding a starting point for this problem. Can anyone give me some advice?

\displaystyle \displaystyle \begin{align*} a^2 - 1 &= 0 \\ (a +1)(a-1) &= 0 \\ a = -1 \textrm{ or }a &= 1 \\ a = 1 \textrm{ or } a &= p - 1 \textrm{ mod }p \end{align*}
• Oct 23rd 2011, 07:14 PM
chisigma
Re: Show that a^2 -1 = 0 mod p has only 2 solutions
Quote:

Originally Posted by restin84
I have an exercise for a course in Cryptography. One of the questions asks us to show that the equation a^2 -1 = 0 mod p has only 2 solutions.

we are told to consider the group Z sub p whose elements are {1,2,.....,p-1}.

I am having a hard time even finding a starting point for this problem. Can anyone give me some advice?

No matter which is p>2, a=1 and a=p-1 always satisfy the congruence equation $\displaystyle x^{2} \equiv 1\ \text{mod}\ p$. In general if we have a congruence equation of the form...

$\displaystyle \sum_{k=0}^{n} a_{n}\ x^{n} \equiv 0\ \text{mod}\ n$ (1)

... then the sum of molteplicities of the roots can't be greater than n...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$