Intereting Posts

A certain “harmonic” sum
Finding the sum $\frac{x}{x+1} + \frac{2x^2}{x^2+1} + \frac{4x^4}{x^4+1} + \cdots$
Can an integral made up completely of real numbers have an imaginary answer?
A function for which the Newton-Raphson method slowly converges?
Probability distribution for finding two values in stages
Representing every positive rational number in the form of $(a^n+b^n)/(c^n+d^n)$
Is it possible to write any bounded continuous function as a uniform limit of smooth functions
Explicit well-ordering of $\mathbb Q$
A series related to $\zeta (3)$.
Find $\lim\limits_{n \to \infty}\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\cdots\left(1-\frac{1}{n^2}\right)$
Why is the Convex Hull property (e..g of Bézier curves) so important?
What is this property relating to logical systems called?
Reducibility of polynomials modulo p
Did I write the right “expressions”?
On a “coincidence” of two sequences involving $a_n = {_2F_1}\left(\tfrac{1}{2},-n;\tfrac{3}{2};\tfrac{1}{2}\right)$

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!

- An analogue of Hensel's lifting for Fibonacci numbers
- Is sum of digits of $3^{1000}$ divisible by $7$?
- Good description of orbits of upper half plane under $SL_2 (Z)$
- Why is $n\choose k$ periodic modulo $p$ with period $p^e$?
- Modular Arithmetic - Pirate Problem
- Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

- Can't come even near to the solution.. Can somebody take a look?
- Describe all integers a for which the following system of congruences (with one unknown x) has integer solutions:
- Finding a primitive root of a prime number
- Find min natural number $n$ so that $2^{2002}$ divides $2001^{n}-1$
- Help with proof of showing idempotents in set of Integers Modulo a prime power are $0$ and $1$
- The cube of any number not a multiple of $7$, will equal one more or one less than a multiple of $7$
- What are the last two digits of $77^{17}$?
- Is sum of digits of $3^{1000}$ divisible by $7$?
- Find all solutions to $x^2\equiv 1\pmod {91}$
- Prove $2^{1092}\equiv 1 \pmod {1093^2}$, and $3^{1092} \not \equiv 1 \pmod {1093^2}$

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

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

- Motivation for different mathematics foundations
- Proving the series of partial sums of $\sin (in)$ is bounded?
- Integrating $\int \frac{\sqrt{\cos 2x}}{\sin x} dx$
- Semisimple ring problem
- Proof of the L'Hôpital Rule for $\frac{\infty}{\infty}$
- Congruence class $$ modulo $m$, $\gcd(x, m) = \gcd(a, m)$
- I want to find all pairs of integer $ (x, y)$
- Prove that $n$ is even.
- Proving The Average Value of a Function with Infinite Length
- A square matrix has the same minimal polynomial over its base field as it has over an extension field
- Why is the decimal representation of $\frac17$ “cyclical”?
- What are the norms in Ito isometry?
- Are there always singularities at the edge of a disk of convergence?
- Did Euclid prove that $\pi$ is constant?
- How to explain brackets to young students