Question

I would like to know how to implement the extended euclidean algorithm in Java which takes 2 integers, public int xgcd(int a, int b) and returns the multiplicative inverse of 'a' modulo 'b' and if the multiplicative inverse of 'a' does not exist it should return -1. I know to do it in a recursive manner but I need help with the non-recursive or iterative manner without using biginteger.math. Something like using the pseudocode would do. I would really appreciate the help. Thank you.

Answer 1

Extended Euclidean Algorithm:

Main.java

import java.util.Scanner;

public class Main

{

public void xgcd(int u, int v)

{

int i = 0, j = 1, x1 = 1, y1 = 0, flag;

while (v != 0)

{

int q = u / v;

int r = u % v;

u = v;

v = r;

flag = i;

i = x1 - q * i;

x1 = flag;

flag = j;

j = y1 - q * j;

y1 = flag;

}

System.out.println("Roots i : "+ x1 +" j :"+ y1);

}

public static void main (String[] args)

{

Scanner sc = new Scanner(System.in);

System.out.println("Extended Euclidean Algorithm\n");

Main m = new Main();

System.out.println("Enter the values for x and y:");

int u = sc.nextInt();

int v = sc.nextInt();

m.xgcd(u, v);

}

}

Output: