2 answers

Euclidean algorithm 3

Question:

Notes: Suppose (a, n) = 1, then there is an integer s such that as = 1 (mod n). This s is called the inverse of a, i.e., a-1 (mod n). The way to find the inverse is asfollows:
1) Use the extended Euclidean algorithm to find s and t such that as + nt = 1;
2) Then a-1(mod n) = s.
In the lecture, we gave an example to find 37-1(mod 121) in three steps.
Step-1: use Euclidean algorithm to get the gcd(121, 37) although we knew it’s one.
Step-2: use extended Euclidean algorithm, which is reverse of Euclidean algorithm, to get s and t, such that 37s + 121t = 1. We got s = 36, t = -11, therefore 37-1(mod121) = 36.
Step-3: verify that 37s = 1 (mod 121). 37×36 = 1332 = 11×121 + 1 = 1 (mod 121), so the congruence 37s = 1 (mod 121) is verified.
Here are the questions for you to solve:
A. Solve the congruence: 15x = 56 (mod 101).
B. Without the aid of a computer or calculating device, find integers x, y, and z such that 35x + 55y + 77z = 1.

Answers

1) Use the extended Euclidean algorithm to find s and t such that as + nt = 1;
2) Then a-1(mod n) = s.
In the lecture, we gave an example to find 37-1(mod 121) in three steps.
Step-1: use Euclidean algorithm to get the gcd(121, 37) although we knew it’s one.
Step-2: use extended Euclidean algorithm, which is reverse of Euclidean algorithm, to get s and t, such that 37s + 121t = 1. We got s = 36, t = -11,therefore 37-1(mod 121) = 36.
Step-3: verify that 37s = 1 (mod 121). 37×36 = 1332 = 11×121 + 1 = 1 (mod 121), so the congruence 37s = 1 (mod 121) is verified.

Here are the questions for you to solve:

A. Solve the congruence: 15x = 56 (mod 101).
B. Without the aid of a computer or calculating device, find integers x, y, and z such that 35x + 55y + 77z = 1.
.

Dear Friend

here is a simple code for it using recursion

int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}

and this site will help u if u want more
http://en.literateprograms.org/Euclidean_algorithm_%28C%29.

Similar Solved Questions

1 answer
Parses theory of human becoming What challenges exist for healthcare institutions to switch to this nursing...
Parses theory of human becoming What challenges exist for healthcare institutions to switch to this nursing approach?...
1 answer
1 pts Question 3 In the figure below, one end of a uniform beam of weight...
1 pts Question 3 In the figure below, one end of a uniform beam of weight 334 N is hinged to a wall; the other end is supported by a wire that makes angles 0 = 25.0° with both wall and beam. Find the tension in the wire (in N). Hinge O 184 605 244 395 O 303 411...
1 answer
Smoky Mountain Corporation makes two types of hiking boots—Xtreme and the Pathfinder. Data concerning these two...
Smoky Mountain Corporation makes two types of hiking boots—Xtreme and the Pathfinder. Data concerning these two product lines appear below:    Xtreme Pathfinder Selling price per unit $ 118.00 $ 84.00 Direct materials per unit $ 65.00 $ 52.00 Direct labor per u...
1 answer
An 45.0 mH inductor is placed in series with a capacitor and a 150 ohm resistor...
An 45.0 mH inductor is placed in series with a capacitor and a 150 ohm resistor to make an RLC circuit. If the resonance frequency of this circuit is 1.52 kHz, what is the value of the capacitance...
1 answer
Required information [The following information applies to the questions displayed below.) The September 30 bank statement...
Required information [The following information applies to the questions displayed below.) The September 30 bank statement for Cadieux Company and the September ledger account for cash are summarized here: BANK STATEMENT Checks Deposits Other $ 100 $3,240 Balance, September 1 September 7 September 1...
2 answers
Analyze the following ethical dilemma from the perspective of rationality and respect (Dilemma Tucker & Marcuson, 1998)
1. Analyze the following ethical dilemma from the perspective of rationality and respect (Dilemma Tucker & Marcuson, 1998). A local nonprofit organization that networks with other service agencies in the area was designed to fill gaps in needed services for families. This agency has been in exis...
1 answer
Which option is correct? a. GRAPH b. histogram c. pareto diagram d. scater diagram e. cause...
Which option is correct? a. GRAPH b. histogram c. pareto diagram d. scater diagram e. cause and effect f. control chart g. check sheet h. Radar chart . The QA manager wouild like to determine the Dest supplier of PVC compound used for the manufacturing of plastic tubes...
1 answer
Show what compounds result from hydrolysis of the following compound.
Show what compounds result from hydrolysis of the following compound. Thanks....
1 answer
7.5.6 Random variables X and Y have joint PDF fx,y(x, y) = _J1/2 -1 < x...
7.5.6 Random variables X and Y have joint PDF fx,y(x, y) = _J1/2 -1 < x <y <1, 1/2 10 otherwise. (a) What is fy(y)? (b) What is fx|v(x\y)? (c) What is E[X|Y = y)?...
1 answer
PLEASE ANSWER ALL QUESTIONS 21-30 21. Of the following, which accurately defines the osmolality of an...
PLEASE ANSWER ALL QUESTIONS 21-30 21. Of the following, which accurately defines the osmolality of an enteral formula? 22. What is the most appropriate recommendation if you have a patient who is presenting with chronic constipation for the first time? 23. Why should you take into consideration th...
1 answer
Question 3 O 1.chi-square O2. Kendall's tau b or Kendall's tau c 03, Goodman and Kruskal's...
Question 3 O 1.chi-square O2. Kendall's tau b or Kendall's tau c 03, Goodman and Kruskal's gamma 。4. r-squared, or eta squared is a statistic that indicates how well a regression model fits the data....
1 answer
26. Dissolving solid NaOH in water is an exothermic process. We can think of this process...
26. Dissolving solid NaOH in water is an exothermic process. We can think of this process like a "reaction" that has AHex = -42 kJ/mol of NaOH. What would be the final temperature of an aqueous solution when 3.0 moles of NaOH is added to 500 mL of water starting at 20 °C? Assume the dens...
1 answer
Un ne teaching Entries and Errors At the end of August, the first month of operations,...
Un ne teaching Entries and Errors At the end of August, the first month of operations, the following selected data were taken from the financial statements of Tucker Jacobs, an attorney: Net income for August 5176,900 Total assets at August 31 961,000 Total abilities at August 31 317,000 Total owner...
1 answer
Figure 3 A cutting 9 m deep is to be excavated in a saturated clay of...
Figure 3 A cutting 9 m deep is to be excavated in a saturated clay of unit weight of 19 kN/m2. The relevant shear strength parameters are Cu 30 kPa and Qu=0. A hard stratum underlies the clay at a depth of 11 m below the ground level. (a) Determine the slope angle at which failure would occur. (b) W...
1 answer
Edugen wileyplus.com 을 Return to Blackboard Advanced Engineering Mathematics, 10th Edition Chapter 8, Section 8.3, Additional Question 01 Incorrect. Is the following matrix symmetric, skew-symme...
edugen wileyplus.com 을 Return to Blackboard Advanced Engineering Mathematics, 10th Edition Chapter 8, Section 8.3, Additional Question 01 Incorrect. Is the following matrix symmetric, skew-symmetric, or orthogonal? Find its spectrum, including any repeated values. A-Г941 -4 1 Enter the ...
1 answer
Allulate e produitwn
allulate e produitwn...
1 answer
Consider a buffer solution that is 0.50 M in NH3 and 0.20 M in NH4Cl. For...
Consider a buffer solution that is 0.50 M in NH3 and 0.20 M in NH4Cl. For ammonia, pKb=4.75. Calculate the pH of 1.0 L upon addition of 0.050 mol of solid NaOH to the original buffer solution. Thanks!...
1 answer
The amount of DNA in a G2 somatic cells is? (assuming the haploid cell of this...
The amount of DNA in a G2 somatic cells is? (assuming the haploid cell of this organism is 3n)? a. 3n b. 12n C. 6n d. 1n e. On QUESTION 2 Which of the following statements about mammalian mitosis is NOT true? a. homologous chromosomes pair up at prophase b. daughter nuclei are genetically identical ...
1 answer
Republic Services (RS) Submit high bid Submit low bid A. Both firms will submit a low...
Republic Services (RS) Submit high bid Submit low bid A. Both firms will submit a low bid in the Nash equilibrium outcome. The firms' managers will be unhappy with this outcome, as they could increase their profits by simultaneously choosing another outcome. O B. Both firms will submit a high bi...