Results 1 to 3 of 3

Math Help - Solving equations mod p^k

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    2

    Question Solving equations mod p^k

    I have to solve such a system of equations:

    a_{11}x_1 + a_{21}x_2 + \ldots + a_{n1}x_n =y_1 (mod  \, p^k)
    a_{12}x_1 + a_{22}x_2 + \ldots + a_{n2}x_n =y_2 (mod  \, p^k)

    \ldots
    a_{1n}x_1 + a_{2n}x_2 + \ldots + a_{nn}x_n =y_n (mod \, p^k)

    p is a prime, k = 1,2,3...
    When k=1 I can use Gauss elimination method, but it doesn't work when k>1 Any ideas, links, pdf's about such equations?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by xoreaxeax View Post
    I have to solve such a system of equations:

    a_{11}x_1 + a_{21}x_2 + \ldots + a_{n1}x_n =y_1 (mod  \, p^k)
    a_{12}x_1 + a_{22}x_2 + \ldots + a_{n2}x_n =y_2 (mod  \, p^k)

    \ldots
    a_{1n}x_1 + a_{2n}x_2 + \ldots + a_{nn}x_n =y_n (mod \, p^k)

    p is a prime, k = 1,2,3...
    When k=1 I can use Gauss elimination method, but it doesn't work when k>1 Any ideas, links, pdf's about such equations?
    This is an interesting problem, and I hope I'm thinking in the right direction. Do we know whether the non-zero coefficients are all coprime to p? (I'm assuming p is prime.) In other words, do we know if the following is true?

    (\forall i,j)(1\le i\le n \land 1 \le j \le n \land a_{ij} \not \equiv 0 \implies \gcd(a_{ij},p)=1)).

    Because if this is true, I'm having a hard time seeing why Gaussian elimination / Gauss–Jordan elimination wouldn't work. When we would normally divide by the leading non-zero coefficient when working in the reals, we will instead multiply by the modular inverse. And if the statement is not true, I'm having a hard time seeing how we would apply Gaussian elimination in the first place. Does this make sense? If not, someone else should come along and post something smarter.

    Edit: Added non-zero condition to \displaystyle a_{ij}.

    Edit 2: [deleted something wrong]

    Edit 3: I've been doing some reading. From here:

    "The Gaussian elimination can be performed over any field."

    We have that \displaystyle \mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p is a finite field (for prime p), but \displaystyle \mathbb{Z}/p^n\mathbb{Z} is only a ring and is distinct from \displaystyle \mathbb{F}_{p^n} (when n > 1). So it seems there could be trouble unless the gcd requirement above is met. (Gaussian elimination just systematizes the way we manipulate linear equations to solve them, with the three elementary row operations.. if Gaussian elimination doesn't work, then what option do we have? Nevertheless it would be nice if I'm wrong and there is a solution method.)

    Edit 4: Sorry for all the edits. I think even if the gcd requirement is met there could be trouble, for example if we have p-1 in one cell and 1 in another cell of the same column and we add them in the course of Gaussian elimination, then that cell will no longer be coprime to p and can cause issues.

    A few references to help people go further if I'm on the right track:

    Wikipedia - Division ring - has multiplicative inverses, and Gaussian elimination is possible
    Article - Gaussian elimination over a euclidean ring - uses row and column operations, apparently; I don't know how that works.
    Last edited by undefined; July 18th 2010 at 06:48 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    2
    Quote Originally Posted by undefined View Post
    Do we know whether the non-zero coefficients are all coprime to p? (I'm assuming p is prime.)
    They are not coprime to p since 1\le a_{ij} \le p^kand this is the main problem since it's impossible to compute
    a_{ij}a_{ij}^{-1}\equiv 1 (mod \, p^k) when \gcd(a_{ij},p^k)=p^{k-s}, s={1,2,\ldots,k})


    Maybe I should concider a_{ij} as elements of Galois field? Gaussian elimination over GF(p^k) will work, but is this the right way to solve such equations?
    Last edited by xoreaxeax; July 19th 2010 at 03:47 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: November 30th 2011, 01:41 AM
  2. Solving equations
    Posted in the Algebra Forum
    Replies: 8
    Last Post: November 13th 2011, 08:59 AM
  3. Solving ln Equations
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: October 2nd 2010, 11:07 AM
  4. solving equations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: July 3rd 2008, 11:05 PM
  5. solving equations
    Posted in the Algebra Forum
    Replies: 4
    Last Post: July 2nd 2008, 10:59 PM

Search Tags


/mathhelpforum @mathhelpforum