1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Division algorithm

  1. Sep 24, 2005 #1
    There's something that's been bothering me with the division algorithm for a while.

    a = dq + r where r < |d| and a,d,q,r are integers. This can be used to find the multiplicative inverse of an integer in Z_m where m is an integer if certain conditions are satisfied. For example if I had two integers 23 and 31, they are relatively prime. So I can find the multiplicative inverse of 31 in Z_23 as follows.

    31 = 1 * 23 + 8
    .
    .
    .
    3*31 - 1 = 4 * 23
    [tex]3 \times 31 \equiv 1\left( {\bmod 23} \right)[/tex]

    So the multiplicative inverse of 31 in Z_23 is 3. How would I go about doing the opposite? That is, finding the multiplicative inverse of 23 in Z_31? With the 'reverse' problem, having done a few questions of this type, I've noticed a pattern where 'multiples' of 31 and 23 in the final equation 3 * 31 - 1 = 4*23 are taken in some combination(can't really recall it right now) and this gives the answer to the 'reverse' problem. I'm not sure if that is just a coincidence or if it is actually meant to work so can someone help me find the multiplicative inverse of 23 in Z_31? The two integers are relatively prime so it should exist. Any help appreciated.
     
  2. jcsd
  3. Sep 24, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What you really want to use are GCDs.
     
  4. Sep 25, 2005 #3
    What you've suggested seems to be what I should be looking at. I come to this conclusion because I have also used the division algorithm to find GCDs. However I still can't make the connection with how to find the multiplicative inverse of 23 in Z_31.

    Some of the steps I omitted in my original post are as follows:

    31 = 1*23 + 8
    23 = 2*8 + 7
    8 = 1*7 + 1
    7= 7*1 + 0

    I'm not sure what I can do here. I'd prefer to be able to use the division algorithm to find the multiplicative inverse if that's possible. Finding GCDs for pairs of 'small' numbers by factorising them is fairly easily but for pairs of large numbers this becomes very difficult. I know that by some theorem, if d is the gcd of two integers a and b then [tex]d = \alpha a + \beta b[/tex] where alpha, beta, a, b and d are integers. But that seems to simply reduce to using the equation 3*31 - 1 = 4 * 23, which is what I had in the first place. I've thought about this but I can't come to a logical conclusion. Could you please provide me with further assistance?
     
  5. Sep 25, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Those are essentially the steps of the (extended) Euclidean algorithm for computing GCDs -- it's very cheap to do.

    Notice that you can reorganize as

    8 = 31 - 23
    7 = 23 - 2*8
    1 = 8 - 7

    and work backwards to get an expression for 1 as a linear combination of 23 and 31. (You might be able to do the bookkeeping in a slightly more clever way)
     
  6. Sep 25, 2005 #5
    Hmm from my original post I have 3*31 - 1 = 4*23.

    What I want is the 'roles' of 31 and 23 switched around. 31 is 23 + 8 and 23 is 31 - 8 so 3*(23+8) - 1 = 4*(31-8) => 3*23 - 1 = 4*31 - 7*8 = 4*31 - 7*(31-23) = > -4 * 23 - 1 = -3*31.

    In other words:

    [tex] - 4 \times 23 \equiv 1\left( {\bmod 31} \right)[/tex]

    So the multiplicative inverse of 23 in Z_31 is [tex] - 4 \equiv 27\left( {\bmod 31} \right)[/tex]. Is the reasoning correct?
     
  7. Sep 25, 2005 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, the multiplicative inverse of 23 is -4, modulo 31.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Division algorithm
  1. Polynomial Division (Replies: 7)

  2. Divisibility test (Replies: 2)

  3. Synthetic Division (Replies: 5)

  4. Voltage division (Replies: 6)

  5. Polynomial division (Replies: 2)

Loading...