You will recall that when we use the Extended Euclidean Algorithm to find the modulo inverse of a number, we must first apply the standard Euclidean Algorithm to find the equation number (starting from Equation 0) that has the last nonzero remainder. This tells us that the value we are looking for is the y-value whose index is two greater than this number (if this value is negative, we just add the modulus one time). For example, if the last nonzero remainder in the standard Euclidean Algorithm occurs in Equation 1, then the inverse value we are looking for is equal to the value of y3. You will also recall that we calculate the values of y as follows:

y0 = 0; y1 = 1; and for all i > 1, yi = yi-2 - (yi-1) (qi-2),

where qi is the quotient in the standard Euclidean Algorithm for Equation i. For example, y2 = y0 - (y1) (q0).

Use the Extended Euclidean Algorithm to find the mod 72 inverse of 5. You must show all work to receive full credit.

Question

Engineering

Charlotte Moody

9 April, 16:01

You will recall that when we use the Extended Euclidean Algorithm to find the modulo inverse of a number, we must first apply the standard Euclidean Algorithm to find the equation number (starting from Equation 0) that has the last nonzero remainder. This tells us that the value we are looking for is the y-value whose index is two greater than this number (if this value is negative, we just add the modulus one time). For example, if the last nonzero remainder in the standard Euclidean Algorithm occurs in Equation 1, then the inverse value we are looking for is equal to the value of y3. You will also recall that we calculate the values of y as follows:

y0 = 0; y1 = 1; and for all i > 1, yi = yi-2 - (yi-1) (qi-2),

where qi is the quotient in the standard Euclidean Algorithm for Equation i. For example, y2 = y0 - (y1) (q0).

Use the Extended Euclidean Algorithm to find the mod 72 inverse of 5. You must show all work to receive full credit.

+2

Answers (1)

Know the Answer?

Jeremiah Mathis · Answer 1

This is the required solution:

Explanation:

To find out the mod 72 inverse of 5, first we need to calculate the gcd of (5,72)

Here I take two variables y and q, started the steps from step 0.

gif. latex? y_%7B_i%7D is the quotient obtained at step i.

As per the algoritham the value of yo=0 y1=1

for i >1 the value gif. latex? y_%7B_i%7D = Yi-2 - gif. latex? y_%7B_i%7D-1 (i-2) (mod n).

Here I am finding the GCD (5, 72)

At step 0 : 72 = 14*5 + 2 14 is quotient, 2 is reminder

step 1 : 5 = 2*2 + 1 2 is quotient, 1 is reminder

step 2 : 2 = 1*2 + 0

If we get the reminder as 1 at yi then we get the inverse of a number mod n at gif. latex? y_%7B_i%7D+2

As per the algorithm y0 = 0 and y1 = 1

The quotients obtained at step 0 and step 1 are represented as q0 and q1 and their values are 14 and 2 respectively.

q0 = 14 and q1 = 2

I got the reminder 1 at step 1, so now the inverse of a number mod n at gif. latex? y_%7B_i%7D+2

i. e., y3

we can find out the value of y2 and y3 by using the equation gif. latex? y_%7B_i%7D = Yi-2 - gif. latex? y_%7B_i%7D-1 (i-2) (mod n)

y2 = y0 - y1 (q0) (mod 72)

= 0-1 (14) mod 72

= - 14 mod 72

= 58

y3 = y1 - y2 (q1) (mod 72)

= 1-58 (2) (mod 72)

= - 115 (mod 72)

= 29

Here we get the y3 value as 29.

The mod 72 inverse of 5 is 29