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? :smile:

[QUOTE=paulunderwood;450114]Is there an easy way to solve x^2 == 1 (mod n)? For n prime it is easy, but what about a composite n? :smile:[/QUOTE]

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.

[QUOTE=paulunderwood;450114]Is there an easy way to solve x^2 == 1 (mod n)? For n prime it is easy, but what about a composite n? :smile:[/QUOTE]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.