1
$\begingroup$

We have this assignment in programming class, but I believe posting it in math will make more sense.

So we're supposed to write a program that takes $n$ equations with each $n$ coefficients, $n\leq10$, as well as 'a value for mod' and then solves the whole thing. Coefficients are supposed to be in $\mathbb{Z}_p^*$, but I don't really know what that is.

Now I have two things I'm not sure about:

  • how exactly is that with the mod supposed to work? I never saw something like that before, just common Gauss elimination. I also heard it only makes sense when the mod value is prime. So how to handle a non-prime mod value?

  • if I have less than $n$ equations left, how could I determine how many solutions the system has?

Thank you for any help.

Edit: to help my understanding of how the process works:

Let's say I have $1x+2y=3 \mod5$ and $2x+3y=4\mod 5$. The result is supposed to be $(4,2)$.

Also, for $1x+2y=4 \mod4$ and $3x+4y=5 \mod4$ the prof's example program crashes. What is going on there that he missed to pay attention to?

  • 0
    Ok, $\mathbb Z_p$ usually stands for the equivalence classes of integers with respect to the $\mod p$ relation. If you do not know what that means, think of $\mathbb Z_p$ as a set of non-negative integers from $0$ to $p - 1$. You add these numbers as usual, but if the result is not within $\mathbb Z_p$, you perform $\mod p$ to get the corresponding number in $\mathbb Z_p$. The same goes for multiplication. The nice property of $\mathbb Z_p$ is every non-zero element has a multiplicative inverse (when $p$ is prime), so it behaves, in a way, like the rational or the real numbers.2012-11-20

0 Answers 0