Solving equations mod p^k

Jul 2010
2
0
I have to solve such a system of equations:

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

\(\displaystyle \ldots\)
\(\displaystyle 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?
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
I have to solve such a system of equations:

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

\(\displaystyle \ldots\)
\(\displaystyle 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?

\(\displaystyle (\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 \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 \displaystyle \mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p\) is a finite field (for prime p), but \(\displaystyle \displaystyle \mathbb{Z}/p^n\mathbb{Z}\) is only a ring and is distinct from \(\displaystyle \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:
Jul 2010
2
0
Do we know whether the non-zero coefficients are all coprime to p? (I'm assuming p is prime.)
They are not coprime to \(\displaystyle p\) since \(\displaystyle 1\le a_{ij} \le p^k\)and this is the main problem since it's impossible to compute
\(\displaystyle a_{ij}a_{ij}^{-1}\equiv 1 (mod \, p^k)\) when \(\displaystyle \gcd(a_{ij},p^k)=p^{k-s}, s={1,2,\ldots,k})\)


Maybe I should concider \(\displaystyle a_{ij}\) as elements of Galois field? Gaussian elimination over \(\displaystyle GF(p^k)\) will work, but is this the right way to solve such equations?
 
Last edited: