number of solution of x*x =1 (mod n) ??

**hingtingchot** · July 4th 2008, 01:02 AM

Hi to all,

I am new to this forum. i want to know the number of solution of the equation x*x = 1 (mod n) for given n.

certainly it is 2 if n is prime if n is non prime I cant figure it out .

I would be gratefull if u help me.

**kalagota** · July 4th 2008, 03:14 AM

Originally Posted by hingtingchot

Hi to all,

I am new to this forum. i want to know the number of solution of the equation x*x = 1 (mod n) for given n.

certainly it is 2 if n is prime if n is non prime I cant figure it out .

I would be gratefull if u help me.

$x^2 \equiv 1 (mod \, n) \Longleftrightarrow x^2 -1 \equiv 0(mod \, n) \Longleftrightarrow (x+1)(x-1) \equiv 0(mod \, n)$

would this help you?

**hingtingchot** · July 4th 2008, 07:24 AM

can u please explain a little bit more ??

**topsquark** · July 4th 2008, 11:11 AM

Originally Posted by kalagota

$x^2 \equiv 1 (mod \, n) \Longleftrightarrow x^2 -1 \equiv 0(mod \, n) \Longleftrightarrow (x+1)(x-1) \equiv 0(mod \, n)$

would this help you?

Originally Posted by hingtingchot

can u please explain a little bit more ??

The equation factors a modulo anything. So there are two solutions: x = 1 and x = -1 = n - 1.

-Dan

**hingtingchot** · July 4th 2008, 11:47 AM

thnx but tthis is only for those n who are pime the solution is 1 and n-1

but say for 8 the solution may be 1,3,5,7 means number of solution is 4 . how could i figure this out ????

thnx in advance

**siclar** · July 8th 2008, 07:15 PM

Right the faulty assumption in topsquark's answer is there being no zero divisors, which is false in this case. Then what satisfies that equation is a pair of zero divisors different by 2. It is clear -1 and +1 work because then (-1+1)(-1-1)=0 and (1+1)(1-1)=0. When else can this happen though?

It is clear that this is exactly when $n=(x+1)(x-1)$ by the modulo. Suppose there is some other y such that $n=(y+1)(y-1)$ . Then $y^2-1=x^2-1$ and so $y=\pm x$ .
So if there are two more solutions exactly when n is the product of consecutive even or odd integers. In other words, when n=8,15,24, etc. More generally, when n=x^2-1 for some integer x. The one exception to this is of course x=2 where n=3.

I think this is correct, I haven't thought through it more than a plausibility thing but it seems correct.

EDIT: Ok, thats not correct. I just randomly picked 12 to see that 5^2=25 which is 1 mod 5 because 4*6=24=0 mod 12. So the multiples are also kind of important... whoops! So in this case we're really looking for x-1, x+1 such that the prime divisors of n are contained in the prime divisors of x-1, x+1. I'll think about it some more.

It also seems to be true for multiples of 4, interestingly enough. Divide it in half to get a 0 divisor, then pick $x=n/2\pm1$ , and this will clearly work. So two special cases clearly give you 4 divisors. Its been two long since I've thought about the nuances of polynomials in this context. At this point perhaps more experimentation would reveal the pattern?

**icemanfan** · July 9th 2008, 03:46 PM

The key is to consider $n = \frac{a^2 - 1}{k}$ for all positive integers a and for all positive integers k that will evenly divide $a^2 - 1$ . For every pair of numbers $(a, k)$ with appropriate k, you get another pair of solutions for n: $(a, n - a)$ . You only need to consider values of a which are less than half of n after the calculation.

Here are the solutions for select composite numbers:

8 - 1, 3, 5, 7

$3^2 - 1 = 8$ gives $(3, 5)$

12 - 1, 5, 7, 11

$\frac{5^2 - 1}{2} = 12$ gives $(5, 7)$

15 - 1, 4, 11, 14

$4^2 - 1 = 15$ gives $(4, 11)$

20 - 1, 9, 11, 19

$\frac{9^2 - 1}{4} = 20$ gives $(9, 11)$

24 - 1, 5, 7, 11, 13, 17, 19, 23

$5^2 - 1 = 24$ gives $(5, 19)$ ; $\frac{7^2 - 1}{2} = 24$ gives $(7, 17)$ ; $\frac{11^2 - 1}{5} = 24$ gives $(11, 13)$

Note also that every solution for a particular number is expressible as $\frac{a^2 - 1}{k}$ . For instance, you may obtain the solutions of 11 for 15 by $\frac{11^2 - 1}{8} = 15$ and 14 for 15 by $\frac{14^2 - 1}{13} = 15$ , but this is unnecessary since you have obtained them from knowing that 1 and 4 are solutions.

I don't really see a more direct way of determining the solutions explicitly; induction doesn't seem to make much sense in terms of this problem. About all you can say for certain is that there are an even number of solutions for every modulus greater than 2, since the solutions come in pairs. You might also say that every number which is a multiple of 4, with the exception of 4 itself, has at least 4 solutions but some numbers (even those that are not multiples of 4) may have more.

**ImaginaryMdA** · May 5th 2013, 04:33 AM

To answer this question it is best to look at the structure of the multiplicative group of order n. For a full review on the subject go to this link: Multiplicative group of integers modulo n - Wikipedia, the free encyclopedia
So since we know that satisfying the equation $x^2=1$ is equivalent to finding an element of order at most 2 in this multiplicative group.
Note that in each cyclic group of even order there are exactly 2 such elements. And also note that if you take the direct product of groups the amount of such elements gets multiplied together to make the grand total of such elements.

So all it comes down to is counting the number of 'terms' this multiplicative group is made of.
so let's count: for each odd prime divisor there is exactly 1 term, and for the prime 2 there is either 2 terms if n is a multiple of 8, or 1 if n is even, (or zero if n is odd).

So this gives the formule $2^{\omega(n)} \epsilon$ where $\epsilon$ is 1 if n isn't a multiple of 8, and 2 otherwhise.

Thread: number of solution of x*x =1 (mod n) ??

LinkBack

Thread Tools

Display

number of solution of x*x =1 (mod n) ??

Patterns in the solutions

Re: number of solution of x*x =1 (mod n) ??

Similar Math Help Forum Discussions

number of solution

number of solution

find the number of solution of this ln equation

number/solution problem

[SOLVED] Complex number solution

Search Tags