Take the 2-minute tour ×

This is for an algorithm I'm working on. Perhaps we can work together!

We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find the variables that satisfy the $n$ equations ($n < p$) of the form:

$\left(\displaystyle\sum_{k=0}^{n-1}{c_k(z_k)^m}\right)\equiv v + m w \bmod{p}$

for each $m$ such that $0\le m < n$. Here $c_k$, $z_k$, $v$, $m$ and $w$ are all integers, but $v$, $w$ and $m$ must be nonzero. Only $n$ is given; we're free to assign variables as we like, with $v$, $w$, and $m$ the slight exceptions. Hopefully this simplifies the problem.

What's the quickest way to solve this problem?


I'd be happy for a quick solution to this easier variation instead. The problem is to find solutions to the modified equation where the sum is taken for $N$ $c_k$s and $z_k$s where $N > n-1$:

$\left(\displaystyle\sum_{k=0}^{N}{c_k(z_k)^m}\right)\equiv v + m w \bmod{p}$

In this variation, there are more variables for the same equivalence, and so it is (much) less constrained.

Any help or suggestions are very much appreciated.

share|improve this question
I'm not sure I understand correctly. If we can choose everything except $n$ freely, why can't we just choose $c_k=v=w=0$? –  joriki Apr 12 '11 at 23:24
Oops, sorry - that's the trivial case. I'll edit the question... –  Matt Groff Apr 12 '11 at 23:27
According to my calculations, the total number of satisfying assignments is 1,725 for $n=2, p=5$ and 7,273 for $n=2, p=7$ and 55,341 for $n=2,p=11$. The amount of satisfying assignments should grow exponentially with $n$. –  Matt Groff Apr 12 '11 at 23:42
I thought I saw a linear algebra method to solving equations like these, outside of modular arithmetic. A similar method would have columns for each $c_k v_j$ over the "domain" of $k$ and $j$, which I tried, but I can't quite get the variables to work in this solution. It would give plenty of freedom in the form of parameters, but I still don't know how to deal with the powers. –  Matt Groff Apr 12 '11 at 23:58
Do you mean this? en.wikipedia.org/wiki/Vandermonde_matrix –  joriki Apr 13 '11 at 0:07

Your Answer



Browse other questions tagged or ask your own question.