Will give lifesaver!! Please help! I have my code written to find GCD(a,n). I\'m

Question

Will give lifesaver!! Please help!

I have my code written to find GCD(a,n). I'm having an extremely difficult time writing a loop to use a dividend, divisor, and the GCD of those two to find a multiplicative inverse using modular arithmetic. I know this is completely off but this is what I have for the loop.:

{if(gcd == 1)
{

q=n/a;
r=n%a;
n=a*q+r;
r=n-a*q;
s=a/r;
t=a%r;
a=r*s+t;
t=a-r*s;
l=a*q;
m=r*s;
k=n-l;
t=a-k*m;
f=(m*l)/odr;
g=odr*f;
h=odd*(-m);



System.out.println(t +" = "+ odr +"*"+ g +" + "+ odd +"*"+ h);
}
else
{System.out.println("There is no multiplicative inverse");
}
}

Explanation / Answer

import java.io.*;import java.util.*;class GCD { public static void main (String args[]) // entry point from OS { int a=0, b=0, d; int sign_a = 1, sign_b = 1; // These are used to handle cases when a < 0 // and/or b < 0, as the extendedEuclid function // assumes that a and b are nonnegative. int[] ans = new int[3]; /* Check for errors, see if user gave enough arguments, etc. */ if (args.length < 2) { System.out.println(" Please input two arguments! "); System.exit(1); } else if (args.length > 0) { try { a = Integer.parseInt(args[0]); } catch (NumberFormatException e) { System.err.println(" Arguments must be integers! "); System.exit(1); } try { b = Integer.parseInt(args[1]); } catch (NumberFormatException e) { System.err.println(" Arguments must be integers! "); System.exit(1); } } /* end of "if" block to catch input errors */ /* Check for input of two zeros, and print error if that's that case */ if ((a == 0) && (b == 0)) { System.out.println(" Oops, both arguments are zero! No GCD of zero! "); System.exit(1); } /* If a and/or b is negative, then track this information for later output, because the extendedEuclid function expects nonnegative input. */ if ( a < 0 ) { sign_a = -1; a = Math.abs(a); } if ( b < 0 ) { sign_b = -1; b = Math.abs(b); } /* Find the answer and print it out */ ans = ExtendedEuclid(a,b); System.out.println(" gcd(" + a*sign_a + "," + b*sign_b +") = " + ans[0]); System.out.print(" " + ans[0] + " = (" + sign_a*ans[1] + ") (" + sign_a*a +")"); System.out.println(" + (" + sign_b*ans[2] + ") (" + sign_b*b + ") "); } public static int[] ExtendedEuclid(int a, int b) /* This function will perform the Extended Euclidean algorithm to find the GCD of a and b. We assume here that a and b are non-negative (and not both zero). This function also will return numbers j and k such that d = j*a + k*b where d is the GCD of a and b. */ { int[] ans = new int[3]; int q; if (b == 0) { /* If b = 0, then we're done... */ ans[0] = a; ans[1] = 1; ans[2] = 0; } else { /* Otherwise, make a recursive function call */ q = a/b; ans = ExtendedEuclid (b, a % b); int temp = ans[1] - ans[2]*q; ans[1] = ans[2]; ans[2] = temp; } return ans; }} /* end of "main" program */

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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