Solving systems of equations modulo n

carpetpool · 2017-02-05, 03:03

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^2-6y = 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.

Nick · 2017-02-05, 09:32

We shall be looking at quadratic equations modulo n shortly in the Basic Number Theory series:
http://www.mersenneforum.org/forumdisplay.php?f=132

CRGreathouse · 2017-02-05, 20:40

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.

2017-02-05, 03:03	#1
carpetpool "Sam" Nov 2016 2·163 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^2-6y = 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 2017-02-05 at 03:12

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Basic Number Theory 18: quadratic equations modulo n	Nick	Number Theory Discussion Group	4	2017-03-27 06:01
New Method for Solving Linear Systems	Dubslow	Miscellaneous Math	24	2012-08-24 10:46
Solving linear systems faster than ever...	WraithX	Math	2	2010-10-23 21:27
solving 2nd order differential equations	Joshua2	Homework Help	9	2009-10-30 07:37
Solving linear systems modulo n	drido	Math	3	2008-02-08 15:06

2017-02-05, 09:32	#2
Nick Dec 2012 The Netherlands 2·7·113 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

2017-02-05, 20:40	#3
CRGreathouse Aug 2006 13511₈ 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.