# 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!

-
Hint: start by separating the cases $c=0$ and $c\neq0$. –  Chris Eagle Jul 17 '11 at 19:58

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

-
Oh right, everything has an inverse! Thanks :D –  badatmath Jul 17 '11 at 20:03
Everything has nothing as an inverse =) haha. Don't forget nothing (namely $0$) doesn't have everything as its inverse. Senseless comment ever. –  Patrick Da Silva Jul 17 '11 at 20:43

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.

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 $$p^n-(p-1)^n.$$ 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.

-