Explanation Procedure used: 1 Consider the situation. 2 Follow the extended Euclidean algorithms. 3 Dictate the conclusion. Extended Euclidean Algorithm. Step 1: Initialization Set r − 1 = m , x − 1 = 1 , y − 1 = 0 , r 0 = n , x 0 = 0 , y 0 = 1 , and i = 0 . Step 2: Apply division algorithm While r i ≠ 0 (a) Replace i with i + 1 . (b) Determine the quotient q i and remainder r i in the division of r i − 2 by r i − 1 . (c) Set x i = x i − 2 − q i x i − 1 and y i = y i − 2 − q i y i − 1 . End while Step 3: output g c d ( m , n ) , x and y Print r i − 1 , x i − 1 , and y i − 1 . Calculation: Consider that the extended Euclidean algorithm is applied to integers m and n , not both 0, and that the last non zero remainder is r k − 1 . Now initialize the extended Euclidean algorithm. Therefore, r − 1 = m , x − 1 = 1 , y − 1 = 0 , r 0 = n , x 0 = 0 and y 0 = 1 . Therefore, it can be written that m x i + n y i = r i for i = − 1 and i = 0 . Therefore, m x i + n y i = r i ; − 1 ≤ i = 0 . Apply the principal of mathematical induction. Consider that m x i + n y i = r is true for all − 1 ≤ i ≤ k − 1 . If i = k − 2 then m x k − 2 + n y k − 2 = r k − 2 … ( 1 ) If i = k − 1 then m x k − 1 + n y k − 1 = r k − 1 … ( 2 ) Since, x k = x k − 2 − q k x k − 1 and y k = y k − 2 − q k y k − 1

5th Edition

ISBN: 9780134689562

Author: Dossey, John A.

Publisher: Pearson,

See similar textbooks

Videos

Question

Chapter 3.2, Problem 33E

To determine

To prove: That mxi+nyi=ri for −1≤i≤k with the help of strong principal of mathematical induction if extended Euclidean algorithm is applied to the integers m and n, not both 0, and that the last nonzero remainder is rk−1.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 3.2, Problem 32E

Chapter 3.3, Problem 1E

Students have asked these similar questions

Determine the moment about the origin O of the force F4i-3j+5k that acts at a Point A. Assume that the position vector of A is (a) r =2i+3j-4k, (b) r=-8i+6j-10k, (c) r=8i-6j+5k

Please answer the questions

Chapter 3 Solutions

Discrete Mathematics

Ch. 3.1 - In Exercises 1–8, find the quotient and remainder...Ch. 3.1 - Prob. 2E Ch. 3.1 - Prob. 3E Ch. 3.1 - In Exercises 1–8, find the quotient and remainder...Ch. 3.1 - In Exercises 1–8, find the quotient and remainder...Ch. 3.1 - Prob. 6E Ch. 3.1 - Prob. 7E Ch. 3.1 - Prob. 8E Ch. 3.1 - Prob. 9E Ch. 3.1 - Prob. 10E

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To prove: That m x i + n y i = r i for − 1 ≤ i ≤ k with the help of strong principal of mathematical induction if extended Euclidean algorithm is applied to the integers m and n , not both 0, and that the last nonzero remainder is r k − 1 .

Videos

To prove: That mxi+nyi=ri for −1≤i≤k with the help of strong principal of mathematical induction if extended Euclidean algorithm is applied to the integers m and n, not both 0, and that the last nonzero remainder is rk−1.

Want to see the full answer?

Chapter 3 Solutions