20161229, 18:24  #1 
Sep 2002
Database er0rr
3,449 Posts 
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?

20161229, 19:10  #2  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
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. 

20161230, 07:34  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·11·307 Posts 
Quote:
Proof: x^21 (mod n) = (x+1)(x1) mod n hence (x+1)(x1) = kn and gcd (x1, 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 nontrivial solutions give nontrivial factorizations. Example 11^2 = 121 == 1(mod 15) => (111)(11+1) = 11k. Indeed, gcd(111,15) = 5 which is a factor of n. In this case k = 6. Last fiddled with by xilman on 20161230 at 07:59 Reason: Add example 

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  20171104 16:53 
Solving systems of equations modulo n  carpetpool  carpetpool  2  20170205 20:40 
Solving x^2 + x + 1 == 0 (mod mp)  paulunderwood  Miscellaneous Math  17  20161231 22:11 
New Method for Solving Linear Systems  Dubslow  Miscellaneous Math  24  20120824 10:46 
solving modular constraints  Joshua2  Homework Help  12  20100219 22:59 