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?

  • 3
    If I understand correctly you are supposed to program the solution of an $n\times n$ system in $\mathbf Z/k\mathbf Z$, where $n$ and $k$ are given on input. If $k$ is prime, all you need in addition to the usual Gaussian elimination ingredients is a routine to compute inverses modulo $k$. If it is not prime, you could do the same (the routine is not much different), but the inverse might not exist, even for values not divisible by $k$; this means that Gaussian elimination may get blocked.2012-11-18
  • 0
    You can also use *all* the "usual" arithmetic operations you usually use in $\,\Bbb Q\,$ *except* multiplication by $\,1/k\,$ , when working $\,\pmod k\,$2012-11-18
  • 1
    @Don, it's not safe to multiply by $1/d$ for any $d$ with $\gcd(d,k)\gt1$.2012-11-18
  • 0
    Good point, @GerryMyerson . I was assuming $\,k\,$ is a prime. Than k2012-11-18
  • 0
    @MarcvanLeeuwen It would be $n\times n+1$ i think, since each equation also has $n+1$ elements (n coefficients and an answer). Thanks for that. keyword to compute inverses mod k is extended euclidian algorithm, right?2012-11-19
  • 0
    @MarcvanLeeuwen oh and the prof writes the elements are in $Z_p^*$. I'm not really sure what that notation refers to.2012-11-19
  • 0
    I believe $p$ is supposed to refer to a prime number as opposed to any natural number. (That may be the reason the second example crashes the program, because $4$ is not a prime number.)2012-11-19
  • 0
    @Tunococ very possible. most non-prime combinations don't crash and have a solution though. Also, in the assignment primes were not mentioned at all (except possibly that $Z_p^*$, which I still don't know what it actually means!)2012-11-19
  • 0
    Yes, some non-prime cases should work. It's the notion of relative primality that's important.2012-11-19
  • 0
    @Tunococ Yes. So ~ what is $Z_p^*$? And do you think you could explain how that solving of - say - the example above would work? I'm really confused by those definitions, what it means to me and what I'm allowed to do, what I'm supposed to do different etc..2012-11-19
  • 0
    The notation $Z_p^*$, or more properly $(\Bbb Z/p\Bbb Z)^\times$, refers to the set of invertible elements in $\Bbb Z$ modulo $p$, and $p$ is no doubt supposed to be prime so that it is also the nonzero elements in $\Bbb Z$ modulo $p$.2012-11-19
  • 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