Chapter 1: Q20E (page 49)

Find the inverse of:. $20 \mod 79, 3 \mod 62, 21 \mod 91, 5 \mod 23$

Short Answer

Expert verified

Inverse of the given numbers is obtained.

Step by step solution

Inverse of 20 mod 79

$\begin{array}{l} GCD (20, 79) \\ 79 = (20 \times 3, 19) \\ 20 = (19 \times 1, 1) \\ GCD (20, 79) = 1 so inverse of 20 \mod 79 \\ So, By backward substitution, \\ 1 = 20 - 1 \times 19 \\ = 20 - 1 \times (79 - 3 \times 20) \\ = 20 - 79 + 3 \times 20 \\ = 4 \times 20 - 1 \times 79 . \\ So, 20^{- 1} = 4 \mod 79 . \end{array}$

Inverse of 3 mod 62

$\begin{array}{l} GCD (3, 62) \\ 62 = (3 \times 30, 2) \\ 3 = (2 \times 1, 1) \\ GCD (3, 62) is 1 so, inverse of 3 \mod 62 is \\ 1 = 3 - 2 \\ = 3 - (62 - 20 \times 3) \\ = 3 - 62 + 20 \times 3 \\ = 21 \times 3 - 62 \times 1 \\ So, 3^{- 1} = 21 \mod 62 . \end{array}$

Inverse of 21 mod 91

$\begin{array}{l} GCD (21, 91) \\ 91 = 21 \times 4, 7 \\ 21 = 7 \times 3, 0 \\ So, Here GCD (21, 91) is 0 so inverse is not possible as per EuclidTheorem \end{array}$

Inverse of 5 mod 23

$\begin{array}{l} \begin{array}{l} GCD (5, 23) \\ 23 = (5 \times 4, 3) \\ 5 = (3 \times 1, 2) \\ 3 = (2 \times 1, 1) \\ GCD (5, 23) is equal to 1 so inverse of 5 \mod 23 \\ 1 = 3 - 2 \\ = 3 - (5 - 3) \\ = 3 \times 2 - 5 \times 1 \\ = (23 - 4 \times 5) \times 2 - 5 \times 1 \\ = 23 \times 2 - 9 \times 5 \end{array} \\ So, 5 - 1 = - 9 = 14 \mod 23 . \end{array}$

Hence, inverse of given numbers is obtained.

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Find the inverse of:. $20 \mod 79, 3 \mod 62, 21 \mod 91, 5 \mod 23$

Short Answer

Step by step solution

Inverse of 20 mod 79

Inverse of 3 mod 62

Inverse of 21 mod 91

Inverse of 5 mod 23

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Data Structures

Data Representation in Computer Science

Theory of Computation

Issues in Computer Science

Computer Systems

Game Design in Computer Science

Study anywhere. Anytime. Across all devices.

Find the inverse of:.20mod79,3mod62,21mod91,5mod23

Short Answer

Step by step solution

Inverse of 20 mod 79

Inverse of 3 mod 62

Inverse of 21 mod 91

Inverse of 5 mod 23

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Data Structures

Data Representation in Computer Science

Theory of Computation

Issues in Computer Science

Computer Systems

Game Design in Computer Science

Study anywhere. Anytime. Across all devices.

Find the inverse of:. $20 \mod 79, 3 \mod 62, 21 \mod 91, 5 \mod 23$