Number of products a * b giving a chosen value n in a finite field Fp

32 Views Asked by At

Given a finite field $F_p$ for a prime number $p$, and a value $n \in F_p$, I was wondering about the number of pairs $(a,b)$ which product equals $n$.

As an example, in $F_7$, and for $n = 4$, there are (to my knowledge) 4 different (distinct) pairs of integers satisfying the relation :

$$2 \times 2 \\ 1 \times 4\\ 5 \times 5\\ 6 \times 3$$

where the two last solutions are the pairs $(-a,-b)$ of the previous solutions. It is quite easily verifiable for small values of $p$, but what about the general case? Is there a result about the number of such pairs? Or at least some (interesting) bounds?

1

There are 1 best solutions below

2
On BEST ANSWER

For $n=0$ the pairs are clearly $$\{ (0,a): a \in \Bbb F_p\}$$ i.e. you have $p$ pairs.

If $n$ is not a square $\pmod p$ (and $n \neq 0$) you have $$\{ (a,b) : ab=n\} = \{ (a, a^{-1}n): a \in \Bbb F_p^{\times} \}$$ has $p-1$ elements. Since you are considering $(a,b)=(b,a)$, simply divide by $2$ and you get that your pairs are $\frac{p-1}{2}$.

In a similar way you can show that, if $n$ is a (nonzero) square $\pmod p$ you have $\frac{p+1}{2}$ pairs.