mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-12-29, 18:24   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,449 Posts
Default Solving x^2==1 (mod n)

Is there an easy way to solve x^2 == 1 (mod n)? For n prime it is easy, but what about a composite n?
paulunderwood is offline   Reply With Quote
Old 2016-12-29, 19:10   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Is there an easy way to solve x^2 == 1 (mod n)? For n prime it is easy, but what about a composite n?
you mean other than the trivial solutions of x=1 and x=-1 both mod n ? solutions if they exist are symmetric mod n x=p and x=-p for example. this comes from the fact that p^even power = (-p)^ even power. if my thought process is correct it would have to do with totatives for the number of solutions possible as most will cause a remainder of a power of their factors. for example mod 12 we have :
0^2=0;
1^2=1;
2^2=4;
3^2 = 9;
4^2=4;
5^2=1;
6^2=0;
7^2=1;
8^2=4;
9^2=9;
10^2=4;
11^2=1;
repeats ... this can be broken down by the chinese remainder theorem as well because for example 4 = 0 mod 2 and 4= 1 mod 3 so what values work mod 12 that way well 4 mod 12 ( okay technically the two right now work for 4 mod 6 adding in the next 2 makes it work mod 12) does because that's when these work together. if the share a common factor other than 1 together then they have to match up mod the other factor to work which just doesn't happen.
science_man_88 is offline   Reply With Quote
Old 2016-12-30, 07:34   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·11·307 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Is there an easy way to solve x^2 == 1 (mod n)? For n prime it is easy, but what about a composite n?
The problem is equivalent to factoring. Find an easy solution to one and you have an easy solution to the other.

Proof: x^2-1 (mod n) = (x+1)(x-1) mod n hence (x+1)(x-1) = kn and gcd (x-1, n) is a factor of n.

The trivial solutions x=\pm 1 give k=0 (mod n) and the trivial factorizations \pm n = \pm (1 * n). The non-trivial solutions give non-trivial factorizations.

Example 11^2 = 121 == 1(mod 15) => (11-1)(11+1) = 11k. Indeed, gcd(11-1,15) = 5 which is a factor of n. In this case k = 6.

Last fiddled with by xilman on 2016-12-30 at 07:59 Reason: Add example
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Solving for x in Phi(n, x) = 0 (mod p) carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-11-04 16:53
Solving systems of equations modulo n carpetpool carpetpool 2 2017-02-05 20:40
Solving x^2 + x + 1 == 0 (mod mp) paulunderwood Miscellaneous Math 17 2016-12-31 22:11
New Method for Solving Linear Systems Dubslow Miscellaneous Math 24 2012-08-24 10:46
solving modular constraints Joshua2 Homework Help 12 2010-02-19 22:59

All times are UTC. The time now is 10:36.

Sat Oct 31 10:36:39 UTC 2020 up 51 days, 7:47, 2 users, load averages: 1.89, 1.93, 1.91

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.