1
$\begingroup$

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

I guess it should be $3(p-2)+1$ modulo $n$ as there are $3$ possibilities for abc to be congruent to $2,\cdots ,p-1$ each and one solution for abc to be congruent to $1$.

  • 0
    What is $n$? Is $p$ prime?2011-07-17
  • 0
    @Mark @Dylan Sorry for the typo. $n$ is $p$ and p is prime2011-07-17
  • 1
    Good stuff. Are you counting rearrangements, or not? If you are, then I think this is $(p - 1)^2$.2011-07-17
  • 2
    $p-1$ ways of picking $a$ (anything but zero modulo $p$); $p-1$ ways of picking $b$. This forces $c$. Total: $(p-1)^2$. If you want distinct *sets* (e.g., if $a=b=1$, $c=x$ is "the same" as $a=c=1$, $b=x$), then it gets more complicated. But your explanation above makes no sense to me at all. Why "3 possibilities for abc to be congruent to 2,...,p-1", and "one" for "1"?2011-07-17
  • 0
    @Aruto this question has a history of duplication, and is in fact based on your answer to the question you linked. See the question: http://math.stackexchange.com/questions/52036/re-can-you-give-me-a-complete-answer-not-just-hint for an explanation of why I did that2011-07-17
  • 0
    As long as $x$ and $p$ are relatively prime, you can choose $a$ and $b$ to be any numbers coprime with $p$, and then choose $c \equiv a^{-1} b^{-1} x \pmod{p}.$ If $x$ and $p$ share, say, $p_1^{r_1} \cdots p_k^{r_k}$ in their factorization (and $x), then you'll have to distribute all those primes to the three - that's ${\sum r_i \choose 3}$ possible ways - and then once again give $b$ and $c$ any to coprime numbers $a'$ and $b'$, then give $c$ a factor of $(ab)^{-1}$.2011-07-17
  • 0
    @Arturo this question has a history of duplication, and is in fact based on your answer to the question you linked. See the question: http://math.stackexchange.com/questions/52036/re-can-you-give-me-a-complete-answer-not-just-hint2011-07-17
  • 0
    @kuchi For $p \neq 2$ there is more than one triple $(a, b, c)$ such that $abc \equiv 1 \bmod{p}$. With $p = 3$, for example, both $(1, 1, 1)$ and $(2, 2, 1)$ work. Are you thinking of additivity from [probability theory](http://en.wikipedia.org/wiki/Probability_axioms#Third_axiom)? I don't see how that could help you here.2011-07-17
  • 0
    @Dylan I see. That invalidates my answer, atleast. Thanks. Ill have to think a bit more about this.2011-07-17

1 Answers 1

2

There are $p-1$ choices for $a$ and $p-1$ choices for $b$ since $a,b$ can be congruent to any nonzero numbers mod $p$. Once $a,b$ are chosen, we must have $c = x(ab)^{-1}$ mod $p$, so there is only one choice for $c$. Overall, there are $(p-1)(p-1)\cdot1 = (p-1)^2$ triples $(a,b,c)$ satisfying the given equation.

Your reasoning in your answer to https://math.stackexchange.com/questions/52036/re-can-you-give-me-a-complete-answer-not-just-hint is not correct. For example, you claim that if $\prod x_i = 1$ mod $p$, then each $x_i$ must be congruent to $1$ mod $p$. But this is not true, e.g. $x_1x_2 = 1$ mod $3$ has two solutions, namely $(1,1)$ and $(2,2)$. So we could have that neither $x_1$ nor $x_2$ is $1$ mod $3$, yet their product is $1$ mod $3$. The other claims that $\prod x_i = 2$ implies that one of the $x$'s is congruent to $2$ mod $p$ and all others are congruent to $1$ mod $p$, and that $\prod x_i = p-1$ implies that one of the $x$'s is congruent to $p-1$ mod $p$ and all others are congruent to $1$ mod $p$ are also wrong. It looks like you treat $x_1,x_2,..,x_n$ as if they were positive integers, but they are not.

Anyway, as many people pointed out, the correct answer to your question is $(p-1)^2$ (unless you meant to ask something different).