 mersenneforum.org Solving x^2==1 (mod n)
 Register FAQ Search Today's Posts Mark Forums Read 2016-12-29, 18:24 #1 paulunderwood   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?    2016-12-29, 19:10   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts Quote:
 Originally Posted by paulunderwood 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.   2016-12-30, 07:34   #3
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3·11·307 Posts Quote:
 Originally Posted by paulunderwood 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  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-11-04 16:53 carpetpool carpetpool 2 2017-02-05 20:40 paulunderwood Miscellaneous Math 17 2016-12-31 22:11 Dubslow Miscellaneous Math 24 2012-08-24 10:46 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