Find the inverse of 79 mod 191using the Extended Euclidean Algorithm

Answered: Find the inverse of 79 mod 191 using…

Advanced Engineering Mathematics

10th Edition

ISBN:9780470458365

Author:Erwin Kreyszig

Publisher:Erwin Kreyszig

Chapter2: Second-order Linear Odes

Section: Chapter Questions

Problem 1RQ

See similar textbooks

Related questions

Question

Find the inverse of 79 mod 191
using the Extended Euclidean Algorithm

Expert Solution

Step 1: Finding the inverse

The symbol $q_{i}$ stands for the quotient obtained in step $i$ .

We'll calculate the auxiliary number $p_{i}$ as we work our way through the Euclidean technique.

This number's value is specified for the first two stages as $p_{0} = 0$ and $p_{1} = 1 .$

We recursively calculate $p_{i} = p_{i - 2} - p_{i - 1} q_{i - 2}$ for the remaining steps $m o d (n)$ .

The Euclidean algorithm's last step is reached by extending this calculation by one step.
In order to begin, the algorithm "divides" $n$ by $x$ .

If the final non-zero residual occurs at step $k,$ then $x$ has an inverse and it is $p_{k + 2}$ if this remainder is $1$ .

$x$ lacks an inverse if the remainder is not $1 .$

$79$ mod $191$

$191 = 2 (79) + 33 p_{0} = 0 79 = 2 (33) + 13 p_{1} = 1 33 = 2 (13) + 7 p_{2} = p_{0} - p_{1} q_{0} = 0 - 2 m o d (191) = 189 13 = 1 (7) + 6 p_{3} = p_{1} - p_{2} q_{1} = 1 - (189 \times 2) = - 377 m o d (191) = 5 7 = 1 (6) + 1 p_{4} = 189 - (5 \times 2) = 179 m o d (191) = 179 6 = 6 (1) + 0 p_{5} = 5 - (179 \times 1) = - 174 m o d (191) = 17 p_{6} = 179 - (17 \times 1) = 162 m o d (191) = 162 ∴ 79 (162) = 12798 = 1 + 67 (191) = 1 m o d (191)$