Results 1 to 4 of 4

Math Help - Solving a congruence

  1. #1
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407

    Solving a congruence

    I was wondering if there was a 'smart' way to solving a congruence like: a^{3} \equiv -1 \: (\text{mod } 31) . This is a sub-problem to an overall problem but I think I'm on the right track. Things to note: there are exactly 3 solutions and all integers with ordre six satisfies the congruence (as a consequence of earlier work).

    I know the solutions are a = 6, 26, 30 but I could only come up with a brute force way of finding them:

    a^{3} + 1 \equiv 0 \: (\text{mod } 31)
    a^{3} + (1 + 31k) = 0 \quad k \in \mathbb{Z}^{+}

    (a+\sqrt[3]{1 + 31k})(a^2 + a\sqrt[3]{1+31k} + (1 + 31k)^{\frac{2}{3}}) = 0

    To attain integer solutions to a, we see that:
    a = \sqrt[3]{1 + 31k}
     a^{3} = 1 + 31k
    k = \frac{a^{3}-1}{31}

    Now it's a matter of testing values of a from 1 to 31 until k is an integer. Luckily, it doesn't take long to find a = 6 works which implies that 6^{5} \equiv 26 works as well.

    This is a rather inelegant way of doing it so is there a better way of doing this or would this suffice?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by o_O View Post
    I was wondering if there was a 'smart' way to solving a congruence like: a^{3} \equiv -1 \: (\text{mod } 31) .
    a^3+1=(a+1)(a^2-a+1) \equiv 0 \mod 31. since 31 is prime, we'll get a \equiv -1 \equiv 30 \mod 31, which is our first solution, or a^2 -a+1 \equiv 0 \mod 31. \ \ \ (1)

    now (1) is equivalent to (2a-1)^2 + 3 \equiv 0 \mod 31, which is equivalent to 9(2a-1)^2 - 4 \equiv 0 \mod 31, which is equivalent to (6a-5)(6a-1) \equiv 0 \mod 31.

    if 6a \equiv 5 \mod 31, then multiplying both sides by -5 gives us a \equiv -25 \equiv 6 \mod 31, and if 6a \equiv 1 \mod 31, then a \equiv -5 \equiv 26 \mod 31. \ \ \ \square
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    120
    If you know a primitive root mod 31 it is fairly simple to find all elements of order 6. (There are 8 primitive roots)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by whipflip15 View Post
    If you know a primitive root mod 31 it is fairly simple to find all elements of order 6. (There are 8 primitive roots)
    The problem is finding the primitive root.
    I find the solution by NonCommAlg to be the best approach.
    But it is not so bad because once the primitive root r is found the index of -1 is then r^{(p-1)/2}.
    Thus, knowledge of the primitive root will basically solve the problem immediately.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving a congruence equation.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 31st 2009, 06:22 AM
  2. solving congruence equations
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 9th 2009, 03:17 PM
  3. Solving a linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 07:54 PM
  4. Solving for x in a quadratic congruence modulo problem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 12th 2009, 09:32 PM
  5. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 06:04 PM

Search Tags


/mathhelpforum @mathhelpforum