mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2017-02-05, 03:03   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 Posts
Post 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
carpetpool is offline   Reply With Quote
Old 2017-02-05, 09:32   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2×32×83 Posts
Default

We shall be looking at quadratic equations modulo n shortly in the Basic Number Theory series:
http://www.mersenneforum.org/forumdisplay.php?f=132
Nick is online now   Reply With Quote
Old 2017-02-05, 20:40   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 12:26.

Tue Nov 24 12:26:40 UTC 2020 up 75 days, 9:37, 4 users, load averages: 1.81, 1.55, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.