Mark DeBonis on Wed, 04 Sep 2013 18:04:54 +0200

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

Thanks so much for the helpful suggestions.

On Wed, Sep 4, 2013 at 12:00 PM, Karim Belabas wrote:
* 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]
`

--
Mark DeBonis
Assistant Professor
Department of Mathematics
Manhattan College
(718) 862-7925