Modular inverse - java coding

Please help. I've been working on this non stop and can't get it right. The issue I'm having is that the output I'm getting for the inverse is always 1.

This is the code that I have (it computes GCD and trying to modify so it also computes a^-1):

import java.util.Scanner;

public class scratchwork
{


    public static void main (String[] args)
    {
        Scanner keyboard = new Scanner(System.in);

        long n, a, on, oa;
        long gcd = 0;

        System.out.println("Please enter your dividend:");
        n= keyboard.nextLong();

        System.out.println("Please enter your divisor:");
        a= keyboard.nextLong();

        on= n;
        oa= a;

        while (a!= 0)
                {gcd=a;
                    a= n% a;
                    n= gcd;
        }

        System.out.println("Results: GCD(" + odd + ", " + odr + ") = " + gcd);

        long vX; vS; vT; vY; q; vR; vZ; m; b;

        vX = n; vY=a;
        vS = 0; vT = 1; m=0; b=0;
        while (a != 0)
        {
            m=vT;;
                b=vX;
                q = n / a;
                vR = vS - q*vT;
      开发者_StackOverflow          tZ = n - q*a;
                vS = vT; n = da;
                vT = tY; dY = vZ;

        }

         if (d>1) System.out.println("Inverse does not exist.");
        else System.out.println("The inverse of "+oa+" mod "+on+" is "+vT);
    } 
}

---

The code you've posted does not declare most of the variables it uses and thus dues not compile. Most importantly, the variable v it uses to output the result is neither defined nor assigned to anywhere in the posted code - whatever it contains has nothing to do with the calculation.

---

Can we see the variables declaration? If you mix integer with double, your numbers can be rounded. Anyway, if you only want the inverse, juste use Math.pow(a, -1);

Also, in the second loop, you never set "a" so it will loop forever:

while (a != 0)
        {
            m=vT;;
                b=vX;
                q = n / a;
                vR = vS - q*vT;
                tZ = n - q*a;
                vS = vT; n = da;
                vT = tY; dY = vZ;

        }

---

@Justin, Thanks. I was able to figure out how to print out the variables in each loop. I basically had to put my loop up with the GCD loop...that was it. 2 weeks worth of work and I had just to move where the loop was.

It works! I'm sorry but I'm doing a happy dance over here.

---

Here's a solution in Python that should be easily translatable into Java:

def euclid(x, y):
    """Given x < y, find a and b such that a * x + b * y = g where, g is the
    gcd of x and y.  Returns (a,b,g)."""
    assert x < y
    assert x >= 0
    assert y > 0

    if x == 0:
        # gcd(0,y) = y
        return (0, 1, y)
    else:
        # Write y as y = dx + r
        d = y/x
        r = y - d*x

        # Compute for the simpler problem.
        (a, b, g) = euclid(r, x)

        # Then ar + bx = g     -->
        #      a(y-dx) + bx = g    -->
        #      ay - adx + bx = g    -->
        #      (b-ad)x + ay = g
        return (b-a*d, a, g)

def modinv(x, n):
    (a, b, g) = euclid(x%n, n)
    assert g == 1

    # a * x + b * n = 1 therefore
    # a * x = 1 (mod n)
    return a%n

It uses the stack, but Euclid's algorithm takes O(log n) steps so you won't have a stack overflow unless your numbers are astronomically high. One could also translate it into a non-recursive version with some effort.