Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let p be a prime number and k be a positive integer. How do I determine the number of solutions to a set of equations in variables $0<=x_1,...,x_n<p^k$? All equations are of the form $\alpha_1x_1+...+\alpha_nx_n \equiv 0 \pmod{p^k}$ for integers $\alpha_1,...,\alpha_n$.

share|cite|improve this question
up vote 2 down vote accepted

You can find not only the number of solutions but also the solutions using Gaussian elimination as follows (working in the ring $\mathbb{Z}/p^k\mathbb{Z}$):

Always select an invertible pivot if possible. The operations in Gaussian elimination don't change the solution set as long as the pivots are invertible. If you encounter a situation in which there's no invertible candidate for the pivot, that means that all candidates contain a factor of $p$. Then you know that the highest digit in the base-$p$ representation of the corresponding variable can be chosen arbitrarily. Then choose a pivot that only has one factor of $p$, and apply elimination like you would "usually", but without multiplying by the common factor of $p$. If there's no pivot with only one factor of $p$, then all candidates have a factor of $p^2$ in common, so you know that the second-highest digit of the corresponding variable can be chosen arbitrarily, and so on.

In this manner, you can perform the entire elimination, always choosing a pivot with the lowest number of factors of $p$, and bring the matrix into row echelon form, which gives you the solution set as usual, keeping in mind that where a pivot isn't invertible, you can choose as many high digits of the corresponding variable arbitrarily as the pivot contains factors of $p$.

share|cite|improve this answer
Can you please tell me what you mean by "invertible pivot" I'm trying to solve a system and this looks like it can be helpful. My question (for which I intend to use this) is here:… – Cedric Mamo Nov 7 '13 at 15:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.