Implement the Pseudo-codes of Euclid’s Algorithm

```.wp-block-code{border:0;padding:0;-webkit-text-size-adjust:100%;text-size-adjust:100%}.wp-block-code>span{display:block;overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc:before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}```int exeuclid(int a, int m)
{
int A3 = m;
int A2 = 0, A1 = 1;

if (m == 1)
return 0;

while (a &gt; 1)
{
// q is quotient
int q = a / m;

int t = m;

// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = A2;

// Update A1 and A2
A2 = A1 - q * A2;
A1 = t;
}

// Make A1 positive
if (A1 &lt; 0)
A1 += A3;
return A1;
}```Code language: JavaScript (javascript)```

Let us look into how to implement Euclid’s algorithm and Euclid’s Extended Algorithms using Java Programming Language.

Euclid’s Algorithm Pseudocode

``````int euclid(int a, int b){
if(b==0)
return a;
else
return euclid(b, a%b);
}```Code language: JavaScript (javascript)```

Euclid’s Extended Algorithm Pseudocode

``````int exeuclid(int a, int m)
{
int A3 = m;
int A2 = 0, A1 = 1;

if (m == 1)
return 0;

while (a &gt; 1)
{
// q is quotient
int q = a / m;

int t = m;

// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = A2;

// Update A1 and A2
A2 = A1 - q * A2;
A1 = t;
}

// Make A1 positive
if (A1 &lt; 0)
A1 += A3;
return A1;
}```Code language: JavaScript (javascript)```

Question

Implement the pseudo-codes of Euclid’s algorithm with recursive function and extended Euclid’s algorithm in any programming language you are comfortable with. Your program should take two integers A and B as inputs and give either as GCD (A, B) = d or B-1 = y.

1) Determine the

a) gcd(72345, 43215)

b) gcd(2740, 1760)

2) Find the multiplicative inverse of

a. 550 mod 1769

b. 7465 mod 2464

c. 42828 mod 6407

Sample Program

``````import java.util.Scanner;
class Lab3{
//euclids algorithm
int euclid(int a, int b){
if(b==0)
return a;
else
return euclid(b, a%b);
}
//euclids extended algorithm
int exeuclid(int a, int m)
{
int A3 = m;
int A2 = 0, A1 = 1;
if (m == 1)
return 0;

while (a &gt; 1)
{
// q is quotient
int q = a / m;

int t = m;

// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = A2;

// Update A1 and A2
A2 = A1 - q * A2;
A1 = t;
}

// Make A1 positive
if (A1 &lt; 0)
A1 += A3;
return A1;
}
public static void main(String[] args) {
Lab3 ob = new Lab3();
int x, y, choice;

Scanner input = new Scanner(System.in);
System.out.println("Enter Choice \n Enter 1 for gcd and 2 for extended ed");
choice=input.nextInt();
switch(choice)
{
case 1:
int output;
System.out.println("Enter the first number");
x = input.nextInt();
System.out.println("Enter the second number");
y = input.nextInt();
output = ob.euclid(x, y);
System.out.println("GCD is:"+output);
break;
case 2:
System.out.println("To Find Inverse");
int m, b;
System.out.println("Enter m");
m=input.nextInt();
System.out.println("Enter b");
b = input.nextInt();
System.out.println("Inverse is equal to: "+ob.exeuclid(m, b));
break;
default:
System.out.println("Wrong Choice");
}

}
}```Code language: JavaScript (javascript)```

Sample Output

You may also like to read: