Please help me with this problem. It needs to be coded in java. Here is an impor

Question

Please help me with this problem. It needs to be coded in java.

Here is an important result about the Greatest Common Divisor of two positive integers: Theorem: If a.b s Z", let S={ k e Z" I k= am+ bn where rn n eZ} . Then gcd(a, b)= min(S) . Thus, 35,t e Z such that gcd(a,b) = as + bt . For example, if a = 28,b = 15, then gcd(28,15)= 1= 28(7)+15(-13); hence, 5= 7and t =-13 are integers that the theorem guarantees to exist. The problem how to find them. Here is a method that is based on the Euclidean Algorithm: Form the matrix [28 ] .15 Since 28div15= 1, subtract the second row from the first row:[1-0 0-1 28-15 ]=[ 1 -1 13] o 1 15 0 1 15 Since 15div13= 1, subtract the first row from the second row: [1 -1 13] [ 1 -1 13] 0-1 1-(-1) 15-13 = -1 2 2 Since 13div2 = 6, subtract 6 times the second row from the first row: [1-6(-1) -1-6(2) 13-6(2) ]=[ 7 -13 1 ] -1 2 2 -1 2 2 Since 2 div1= 2, subtract 2 times the first row from the second row: [7 -13 1] [ 7 -13 1 ]-1-2(7) 2-2(-13) 2-2(1) = -15 28 0 At this point we are done because the second row has a zero in the third C01UllUl. The desired values are in the first row 5= 7,t = -13 , and d = 1. Infact, all possible values of sand t can also be found! 285+ 1St= 1= gcd(a,b) if and only if 5 = 7-15k and t = -13+ 28k. illgeneral, you need to repeat steps similar to steps 2 - 5 until a zero appears in the third column as in If the zero is in the first row, then the second row contains the values s, t and d; otherwise, the these values are in the first row, Using the ideas of the example above, write a program that requests the user to enter to positive integers a and b and computes and prints the gcd(a,b) along with values for sand t such that gcd(a,b) = as +bt .

Explanation / Answer

import java.util.*;

class Main
{
public static void main(String[] args)
{
int a,b;
Scanner in = new Scanner(System.in);
System.out.println(" enter the values of a and b");
a = in.nextInt();
b = in.nextInt();
int[][] z = new int[2][3];
// form matrix here.
for(int i=0; i<2; i++)
z[0][0] = 1;
z[0][1] = 0;
z[0][2] = a;
z[1][0] = 0;
z[1][1] = 1;
z[1][2] = b;
print_matrix(z);
int factor;
//start doing operations here;
while(z[1][2] !=0 )
{
//since we got factor now start substration.
if(z[0][2] > z[1][2])
{
factor = z[0][2]/z[1][2];
System.out.println( " substrating " + factor + " times the second row from first row " );
for(int j=0; j<3; j++)
z[0][j] = z[0][j]- factor*z[1][j];
}
else
{
factor = z[1][2]/z[0][2];
System.out.println( " substrating " + factor + " times the first row from second row " );
for(int j=0; j<3; j++)
z[1][j] = z[1][j]- factor*z[0][j];
}
if(z[0][2] ==0) break;
print_matrix(z);
} //end while loop
if(z[1][2] == 0)
System.out.println(" required values are s = " + z[0][0] + " and t = " + z[0][1]);
if(z[0][2] == 0)
System.out.println(" required values are s = " + z[1][0] + " and t = " + z[1][1]);


}
//end main
public static void print_matrix(int[][] z)
{
System.out.println();
for(int i=0; i<2; i++)
{
for(int j=0; j<3; j++)
{
System.out.print(" " + z[i][j]);
}
System.out.println();
}

}

//end print method
}
// end class

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.