Results 1 to 8 of 8

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

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    3

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

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by hingtingchot View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2008
    Posts
    3
    can u please explain a little bit more ??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,100
    Thanks
    379
    Awards
    1
    Quote Originally Posted by kalagota View Post
    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?
    Quote Originally Posted by hingtingchot View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2008
    Posts
    3
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2008
    Posts
    81
    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?
    Last edited by siclar; July 8th 2008 at 07:44 PM. Reason: Wrong! haha
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092

    Patterns in the solutions

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2013
    From
    Belgium
    Posts
    1

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

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of solution
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 2nd 2011, 09:52 AM
  2. number of solution
    Posted in the Calculus Forum
    Replies: 0
    Last Post: January 3rd 2011, 12:56 AM
  3. Replies: 19
    Last Post: February 15th 2009, 07:17 AM
  4. number/solution problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: August 18th 2008, 09:25 AM
  5. [SOLVED] Complex number solution
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: January 23rd 2008, 09:39 AM

Search Tags


/mathhelpforum @mathhelpforum