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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Experts in algebra please help: we would like to know the number of solutions for this set of six of modular N algebraic equations:

$$ (1) \quad x_1 y_2 \equiv x_2 y_1 \pmod{N}\\ (2) \quad x_1 y_3 \equiv x_3 y_1 \pmod{N}\\ (3) \quad x_4 y_1 \equiv x_1 y_4 \pmod{N}\\ (4) \quad x_2 y_3 \equiv x_3 y_2 \pmod{N}\\ (5) \quad x_2 y_4 \equiv x_4 y_2 \pmod{N}\\ (6) \quad x_3 y_4 \equiv x_4 y_3 \pmod{N} $$ Suppose that all variables are modulo $N$. Here there are eight variables in total, $x_1,x_2,x_3,x_4, y_1,y_2,y_3,y_4$.


(a) For $N=2$, how many independent solutions there are?

(b) For $N=3$, how many independent solutions there are?

(c) For a generic prime number $N$, how many independent solutions there are?

I emphasize these questions about counting number(how many) of independent solutions, so explicit solutions for these equations are NOT required.

Hint (what I have known): the 6 constraint equations are not independent, actually the first equations (1),(2),(3) can guarantee the last three (4)(5)(6)equations. So counting the number of degrees of freedom, roughly the number of independent solutions are about

$$ \text{ the number of independent solutions} \geq N^{8-3}=N^5 $$

On the other hand, if we set all $x_1,x_2,x_3,x_4=0$, then there are free choices for $y_1,y_2,y_3,y_4$ (which provides $N^4$ solutions). Similarly, if we set all $y_1,y_2,y_3,y_4=0$ , then there are free choices for $x_1,x_2,x_3,x_4$ (which provides $N^4$ solutions, but overlap one solution such that all $x=y=0$ counted earlier once.), so roughly the number of independent solutions are about

$$ \text{ the number of independent solutions} \geq 2\;N^{4}-1 $$

So what is the exact number expression of this number of independent solutions?

share|cite|improve this question
the other possibility is solving it numerically or by Mathematica.… – annie heart Apr 12 '14 at 22:52
my conjecture is that the number of independent solutions=$N^4+N^5$, can someone disprove or prove it? :o) – annie heart Apr 12 '14 at 23:02
Sorry, I made a mistake, yes, I agree with Idear's result. – miss-tery Apr 13 '14 at 1:01
up vote 2 down vote accepted

I have numerically computed, there is no better intuition for me, but your guess $N^4+N^5$ is close. Let us say the number of independent solutions $\equiv Sol(N)$, then

$$ Sol(2)=46=2^4+2^5-2 $$ $$ Sol(3)=321=3^4+3^5-3 $$ $$ Sol(5)=3745=5^4+5^5-5 $$ $$ Sol(7)=19201=7^4+7^5-7 $$

thus my conjecture is that for the prime $N$ $$ Sol(N)=N^4+N^5-N $$ I hope it helps.

share|cite|improve this answer
Thank you +1, let me take a look. :o) – annie heart Apr 12 '14 at 23:40
it does not work for the non-prime $N$ though. – Idear Apr 12 '14 at 23:41
The credit is given to Idear unless someone comes up with an analytic counting solution. – annie heart Apr 13 '14 at 19:57

Modulo a prime $N$, the integers form a field. For simplicity, use conventional algebraic notation (equals, forget about modulus). Take first the case that $x_1$ and $y_1$ aren't zero, then your first three equations reduce to: \begin{align} \frac{x_2}{x_1} &= \frac{y_2}{y_1} \\ \frac{x_3}{x_1} &= \frac{y_3}{y_1} \\ \frac{x_4}{x_1} &= \frac{y_4}{y_1} \end{align} So you can define the three ratios independently ($N^3$ options), and then fix the values of $x_1$ and $y_1$ at will ($(N - 1)^2$ options), so the total is $N^3 (N - 1)^2$. If $x_1 = 0$, then either $y_1 = 0$ and $x_2$, $x_3$ are arbitrary ($N^2$ options) or $y_1 \ne 0$ ($N - 1$ possible values) and $x_2$, $x_3$, $x_4$ arbitrary ($N^3$ options).

Adding all up gives $N^3 (N - 1)^2 + N^2 + (N - 1) N^3 = N^5 - N^4 + N^2$.

share|cite|improve this answer
It is nice you have explicit analytic result, +1. But my numerical check is also consistent with Idear's, do you know why? maybe there is some missing part in yours? Thanks. :o) – annie heart Apr 12 '14 at 23:58
there are tricky things that when some of $x,y$ values are zeros, we may need to be careful that Eq.(1)~(3) may not fully account Eq.(4)~(6), isn't it? – annie heart Apr 12 '14 at 23:59
I might have over/undercounted somewhere. – vonbrand Apr 12 '14 at 23:59

Your Answer


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.