20170205, 03:03  #1 
"Sam"
Nov 2016
2×3×53 Posts 
Solving systems of equations modulo n
Like in algebra, how would one solve for x and y in:
4xy = 1 mod 29 2xy^2 = 1 mod 29 Yeah, the solution is obvious and easy in this one, how about when adding or subtracting terms? x^26y = 1 mod 210 3y^2+10y+12x = 1 mod 210 Which one would seem easier to solve? For both of them, I would go for substitution algebraic method, since the only constant (of degree 0) we are dealing with here in both equations is 1. but I don't know any better. Any help, feedback, or similar equations are appreciated here. Thanks. Last fiddled with by carpetpool on 20170205 at 03:12 
20170205, 09:32  #2 
Dec 2012
The Netherlands
2×3^{2}×83 Posts 
We shall be looking at quadratic equations modulo n shortly in the Basic Number Theory series:
http://www.mersenneforum.org/forumdisplay.php?f=132 
20170205, 20:40  #3 
Aug 2006
2·2,969 Posts 
Working mod primes is easy since you have the field structure  it's just like working over the reals, you can add, subtract, multiply, and divide. Mod prime powers you do much the same thing but then use Hensel lifting. Mod composites you can use the CRT to reduce to prime powers.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 18: quadratic equations modulo n  Nick  Number Theory Discussion Group  4  20170327 06:01 
New Method for Solving Linear Systems  Dubslow  Miscellaneous Math  24  20120824 10:46 
Solving linear systems faster than ever...  WraithX  Math  2  20101023 21:27 
solving 2nd order differential equations  Joshua2  Homework Help  9  20091030 07:37 
Solving linear systems modulo n  drido  Math  3  20080208 15:06 