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?

.

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 .

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 is a finite field (for prime p), but is only a ring and is distinct from (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.