Solutions of $\prod_{i=1}^n x_i = c$ mod p

The problem is: Given constants $c$ and $n$, how many solutions are there to $\prod_{i = 1}^n x_i = c$ mod p?

This is the sort of thing that seems like it should be easy but I really have no idea how to do it. Can you give me a hint or two?

Thank you very much!

Solutions Collecting From Web of "Solutions of $\prod_{i=1}^n x_i = c$ mod p"

If $c\equiv 0\pmod{p}$, then at least one of the $x_i$ must be equal to $0$ modulo $p$ and the rest don’t matter. Count how many solutions there are with exactly $j$ of the $x_i$ equal to $0$, $1\leq j\leq n$, and add them up.

If $c\not\equiv 0\pmod{p}$, then no $x_i$ can be equal to $0$. If the values of $x_1,\ldots,x_{n-1}$ are chosen arbitrarily, can you always find an $x_n$ such that the product will equal $c$ modulo $p$? If so, count the number of ways of selecting $x_1,\ldots,x_{n-1}$, and how many values of $x_n$ will work. If not, you’ll have to think of some other way…

The question asks for the number of solutions of
$$\prod_{i=1}^n x_i = c \bmod{p}.$$
The above notation is more common in Computer Science than in Mathematics. I am more comfortable with the usual mathematical notation, so will use it instead.

Please note that this is a minor elaboration of Arturo Magidin’s already quite complete answer. Any upvotes should be directed to that answer, not this one.

I assume that you are asking for the number of ordered $n$-tuples $(x_1,x_2,\dots, x_n)$ such that: (i) each $x_i$ is an integer, with $0 \le x_i \le p-1$ and (ii) $\prod_{i=1}^n x_i \equiv c \pmod{p}$. If it is unordered $n$-tuples (multisets) that you are interested in, the problem becomes vastly more complicated.

There are two entirely different cases, depending on whether $c \equiv 0 \pmod{p}$ or $c \not\equiv 0 \pmod{p}$.

Case $c$ is congruent to $0$: A product $\prod x_i$ is congruent to $0$ modulo a prime $p$ if and only if at least one of the $x_i$ is congruent to $0$ modulo $p$. In our case, the numbers $x_i$ range from $0$ to $p-1$, so we want to count the number of $n$-tuples $(x_1,x_2,\dots,x_n)$ such that at least one of the $x_i$ is equal to $0$.

Call such an $n$-tuple good. We want to count the number of good $n$-tuples. It is easier to count the number of bad $n$-tuples. An $n$-tuple is bad if it is not good, that is, if it has no $0$’s. So the bad $n$-tuples are the ones where all the $x_i$ are selected from the set $\{1,2,\dots,p-1\}$. Thus we want to count the number of “words” of length $n$ over an “alphabet” of $p-1$ letters. There are $(p-1)^n$ such words, so there are $(p-1)^n$ bad $n$-tuples.

The total number of $n$-tuples is $p^n$. We know how many of them are bad. We conclude that the number of good ones is
That is our answer. Note that the strategy of counting the bad guys is often useful in counting problems.

Another way: We sketch another approach. In order to be bad, a sequence has to have $1$, or $2$, or $3$, or $\dots$ or $n\:$ $0$’s. How many sequences are there with $k$ $0$’s? The location of these $0$’s can be chosen in $\dbinom{n}{k}$ ways. For every such choice, we can fill the remaining $n-k$ spots with non-zero numbers in $(p-1)^{n-k}$ ways, so the number of sequences with exactly $k$ $0$’s is $\dbinom{n}{k}(p-1)^{n-k}$.

Now add up. We get a long sum, which maybe could be taken as the answer. But if you know the Binomial Theorem, the long expression simplifies enormously. Except for the “missing” first term of $\dbinom{n}{0}(p-1)^n$, it is the binomial expansion of $((p-1)+1)^n$. So our long answer simplifies to $p^n-(p-1)^n$.

Case $c$ is not congruent to $0$: From your remarks, I think you understand the number theory that is needed. Let $(x_1, x_2, \dots, x_{n-1})$ be any sequence of $n-1$ numbers, where each $x_i$ is between $1$ and $p-1$ (inclusive).

Let $y_{n-1}$ be the product of these $x_i$. Then there is a unique number $x_n$ in our interval such that $y_{n-1}x_n \equiv c \pmod p$. This number $x_n$ is (congruent to) $y_{n-1}^{-1}c$, where $y_{n-1}^{-1}$ is the multiplicative inverse of $y_{n-1}$.

Thus $x_1, x_2, \dots, x_{n-1}$ can be chosen absolutely freely from $\{1,2, \dots,p-1\}$, and for every choice of these, there is exactly one $x_n$ that completes them to an $n$-tuple that works.

It follows that the number of $n$-tuples that we are looking for is precisely the same as the number of words of length $n-1$ that can be formed using the alphabet $\{1,2, \dots,p-1\}$. And there are $(p-1)^{n-1}$ such words.