Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
Hint: start by separating the cases $c=0$ and $c\neq0$. –  Chris Eagle Jul 17 '11 at 19:58
add comment

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
Oh right, everything has an inverse! Thanks :D –  badatmath Jul 17 '11 at 20:03
1  
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
add comment

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.

share|improve this answer
1  
Thanks for the nice answer :) Why no upvotes? –  badatmath Jul 18 '11 at 5:20
    
Is that what the CW option is for? I admit that I've never tried it. –  Dylan Moreland Jul 18 '11 at 5:48
    
@Andre: One possible use of Community Wiki is to do it so that your reputation will not benefit (or hurt) from up or down-votes. It might be the sensible thing to do here, replacing the "no up votes" with a comment saying why you've turned it into a CW post; it lowers the rep requirements for others to edit it, and has other side-effects, but I don't think it's a bad way to go. I've done it on occasion with answers that I don't think are substantial enough. –  Arturo Magidin Jul 18 '11 at 17:19
    
@Andre: It's not what I wish or not; I respect your decision of how to proceed. I'm just offering some comments and a viewpoint for you to consider in making your decision as you see fit, since I've used the CW option for that purpose myself from time to time. As I said, it's not what I "wish" or not, just thought to give you some more information to inform your decision. –  Arturo Magidin Jul 18 '11 at 17:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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