Re: solve system of linear equations mod p - more than one solution

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2013-09-04 13:37]:
> On Tue, Sep 03, 2013 at 08:40:19AM -0400, Mark DeBonis wrote:
> > Is PARI able to solve a system of linear equations modulo p which have more
> > than one solution? (there are free variables)  Can it list the complete
> > solution set in some manner?  Can you choose which variables to solve for?
> 
> Yes, use matinverseimage and matker. 
> For example:
> ? p=101;A=[1,2,3;4,5,6]*Mod(1,p);B=[7,8]~*Mod(1,p);
> ? S=matinverseimage(A,B)
> %11 = [Mod(61,101),Mod(74,101),Mod(0,101)]~
> ? K=matker(A)
> %12 = [Mod(1,101);Mod(99,101);Mod(1,101)]
> ? S+K*[lambda]~
> %13 = [Mod(1,101)*lambda+Mod(61,101),Mod(99,101)*lambda+Mod(74,101),Mod(1,101)*lambda]~

And if 'p' is not prime (or even if each equation involves different
not-necessarily-coprime moduli), you can use (the vastly less efficient)
matsolvemod():

  ? N=102;A=[1,2,3;4,5,6];B=[7,8]~;
  ? matsolvemod(A,B, N)    \\ one integer solution
  %2 = [-5, -2, 2]~ 
  ? matsolvemod(A,B, N, 1) \\ all integer solutions
  %3 = [[-5, -2, 2]~, [0, -1, -11; 2, 0, -2; 1, -2, 5]]


Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`