I'm dealing with a problem here. The problem is as follows:

There is a set $Z_p=\{0,1,2,3,...,p-1\}$ where $p$ is a prime.

From this set we form a new set $B=\{x+x^{-1}\mid x\in Z_p\}$, where the inverse of x is x^-1=a that fulfills the condition ax=1(mod p)

The question is: What is the cardinality of set B?

I have found that the cardinality is $\dfrac{p+1}{2}$ but I don't know how to prove it.

This is my idea of proof: Let's denote $Z_i$ to be the set of all inverses of $Z_p$; for example $Z_5=\{0,1,2,3,4\}\implies Z_i=\{1,3,2,4\}$.

We know that $0$ has no inverse so there are only $(p-1)$ elements left to find and inverse. Also, number $1$ has the inverse $1$ and number $(p-1)$ has the inverse $(p-1)$.

We are left with $(p-3)$ elements to find the inverse. From this the set $B$ is going to have a cardinality of $2+\dfrac{p-3}{2}=\dfrac{p+1}{2}$, because half of the $(p-3)$ elements are not taken in operation because they form the same number; for example $Z_5=\{0,1,2,3,4\}$ and $Z_i=\{1,3,2,4\}$. Now, B={1+1 (mod 5), 2+3(mod 5), 4+4(mod 5)}; 3+2(mod 5) is not taken because it is equal to 2+3(mod 5)

What I'm trying to prove now is that there are no two pairs $x$ and $x^{-1}$ that have the same result modulo $p$. If this is proven than it is proven that the cardinality of set $B$ is $\dfrac{p+1}{2}$.

• Can someone tell me if I'm in the right way and give me some help? Thank you!

This is a good question, I confirm that you're in the write way,Let $f:\mathbb{Z_p}^*\to\mathbb{Z_p}^*$ be the function defined by $f(x)=x+x^{-1}$, now what you need to prove is $f(x)=f(y)$ if and only if $x=y$ or $x=y^{-1}$ ( all equalities are considered in the field $\mathbb{Z_p}^*$)

we have $$f(x)-f(y)=(x-y)+(x^{-1}-y^{-1})=(x-y)(1-(xy)^{-1})$$

hence $f(x)-f(y)=0$ implies $x-y=0$ or $1-(xy)^{-1}=0$ (because in a field $ab=0$ implies $a=0$ or $b=0$) finally $x=y$ or $x=y^{-1}$.

we conclude that $x+x^{-1}$ and $y+y^{-1}$ are never the same except if $y=x^{-1}$ or $y=x$.

• From what you are saying does it mean that two numbers have the same result modulo p if and only if they are equal? – Student Mar 15 '15 at 22:38
• When i did my calculus i did all equalities modulo $p$ so every equality in the post is an equality $\mod p$ – Elaqqad Mar 15 '15 at 22:57