Code covered by the BSD License  

Highlights from
System of linear congruences

5.0

5.0 | 1 rating Rate this file 15 Downloads (last 30 days) File Size: 3.06 KB File ID: #32856
image thumbnail

System of linear congruences

by

 

11 Sep 2011 (Updated )

Solution to Simultaneous Linear Congruences

| Watch this File

File Information
Description

X = LINCON(A,B,N) solves the system of linear congruences
 
A(1) * X == B(1) (mod N(1))
A(2) * X == B(2) (mod N(2))
   ...
A(m) * X == B(m) (mod N(m))
 
The solution, X, will be given as a vector [x1 x2] representing the general solution
 
   X == x1 (mod x2)
   
Any specific answer can be found by letting X = x1 + x2 * k for any integer value of k.
 
If no solution exists [NaN NaN] will be returned.
 
A scalar input functions as a constant vector of the same size as the other inputs.
 
Program is compatible with Variable Precision Integer Arithmetic Toolbox available on File Exchange (#22725) Use of VPI is recommended for large magnitude inputs or outputs. If VPI is not used and internal calculations exceed largest consecutive flint a warning will be given that results may be inaccurate, along with [NaN NaN].
 
Example #1:
Solve the following system of linear congruences
   2x == 2 (mod 6)
   3x == 2 (mod 7)
   2x == 4 (mod 8)
 
Solution:
   a=[2 3 2]; b=[2 2 4]; n=[6 7 8];
   x=lincon(a,b,n)
 
Verify:
   isequal( mod(a*x(1),n) , b)
 
 
Example #2:
   Use of VPI for large magnitude numbers. Solve the following system of linear congruences
   (1234567)x == 89 (mod 2^32)
   (9876543)x == 21 (mod 3^50)
   (5555)x == 62830211 (mod 7^10)
 
Solution:
   a=[1234567 9876543 5555]; b=[89 21 62830211];
   n=[vpi(2)^32 vpi(3)^50 vpi(7)^10];
   x=lincon(a,b,n)
 
Verify:
   isequal( mod(a*x(1),n) , b)

Acknowledgements

Variable Precision Integer Arithmetic inspired this file.

MATLAB release MATLAB 7.12 (R2011a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (1)
01 Dec 2011 Su Dongcai  
Updates
04 Apr 2012

Updated help section

Contact us