先看高斯消元的每一次消元，首先得到(假设消到了第i行了,i>=0)
{0,0,..0,C[i],C[i+1],C[i+2]...}
然后需要用它去"消"下面的若干行的第k项
可以知道在同余状况下,假设有
C[k]*x[k] = B[i] ( mod P)
同时假设下面的某一行
C'[k]*x[k]= B'[i] ( mod P)
我们在消元的过程中是希望把他们消掉的,可是由于是在同余系下，所以必须保证操作都是整数！
下面可以做参考
第1种方法:
求出L=LCM(C[k],C'[k]),并记D[k]=L/C[k],D'[k]=L/C'[k],我们把C'[k]对应的方程同时乘上D'[k] (这显然不会对解造成影响),然后再把C[k]对应的拿去乘上D[k],然后相减,对于j>i,显然有
(假设我是第i行的减去下面的行):新的C''[j] = (L-C'[j]*D'[k])( mod P)
最后得到了消完元的,然后对于最后一项:
C[n-1]*x[n-1] = B[n-1] (mod P)
它的解的个数为G=GCD(C[n-1],P)(前提是G|B[n-1])
然后慢慢回带

第2种方法:
如果P是素数或square-free 数，那么可以使用乘法逆元来避免求LCM

以上只是我的思路，不知对否，你可以参考一下