# 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.

#### Similar Solved Questions

##### 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 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...
##### 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...
##### 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...
##### 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...
##### 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...
##### 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...
##### Show what compounds result from hydrolysis of the following compound.
Show what compounds result from hydrolysis of the following compound. Thanks....
##### 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)?...
##### 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...
##### 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....
##### 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...
##### 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...
##### 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...
##### 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 ...