Java/EuclideanAlgorithm.Java at master · sureyyaakis/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

importjava.util.*;
importjava.lang.*;

classMain {

// Java program to demonstrate working of extended
// Euclidean Algorithm
// extended Euclidean Algorithm


publicstaticintgcdExtended(inta, intb, intx, inty)
	{
// Base Case
if (a == 0)	{
x = 0;
y = 1;
returnb;
 }

intx1=1, y1=1; // To store results of recursive call
intgcd = gcdExtended(b%a, a, x1, y1);

// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;

returngcd;
	}

// Driver Program
publicstaticvoidmain(String[] args)
	{
intx=1, y=1;
inta = 35, b = 15;
intg = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);

	}
}