| Mark DeBonis on Wed, 04 Sep 2013 18:04:54 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: solve system of linear equations mod p - more than one solution |
* Bill Allombert [2013-09-04 13:37]:
And if 'p' is not prime (or even if each equation involves different> 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]~
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]
`