3
$\begingroup$

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!
$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.