Use Euclid’s algorithm and backwards substitution to determine the
multiplicative inverse of 27 in Z40 .
I've worked out;
40 = 1*27 + 13
27 = 2*13 + 1
Then rearranged to make the remainders the subject.
1 = 27-2*13
1 = 2(40-1*27)
Bit confused where to go from here...
To determine the multiplicative inverse of 27 in Z40 using Euclid's algorithm and backwards substitution, you've correctly worked out the steps so far. Let's continue from where you left off:
1 = 2(40 - 1*27)
Now, let's simplify this equation further:
1 = 2*40 - 2*27
Next, we can rearrange this equation to get 27 in terms of 1:
1 = -2*27 + 2*40
Since we're interested in finding the multiplicative inverse, we want to express 27 as a multiple of 40 minus 1. In this case, 40 and -1 are the coefficients we need.
Now, we can substitute 27 by its expression in the equation:
1 = -2(27) + 2(40)
By comparing this equation to the form ax + by = gcd(a, b), we can see that a = -2 and b = 2. In this case, the greatest common divisor (gcd) is 1, as seen in the previous steps.
To find the multiplicative inverse of 27, we need to interpret the coefficients of 27 in the equation in terms of Z40. In other words, we need to find the value that, when multiplied by 27, results in 1 (mod 40).
Therefore, the multiplicative inverse of 27 in Z40 is -2 (or equivalently, 38), since -2 * 27 = 54 ≡ 1 (mod 40).
So, the answer is -2 or 38.
To determine the multiplicative inverse of 27 in Z40 using Euclid's algorithm and backwards substitution, we can start from where you left off:
1 = 2(40 - 1*27)
Now, we can rewrite this equation to isolate the remainder for step-by-step substitution:
1 = 2*40 - 2*27
Next, we substitute the remainder from the previous step:
1 = 2*40 - 2*(27 - 2*13)
Simplifying this equation gives us:
1 = 2*40 - 2*27 + 4*13
Now, we can arrange the terms to express 27 as a combination of 40 and 13:
1 = (-2)*27 + 4*13
Finally, we rewrite 27 as its remainder in terms of 40 and 13:
1 = (-2)*27 + 4*(40 - 1*27)
Simplifying this equation further:
1 = (-2)*27 + 4*40 - 4*27
1 = 4*40 - 6*27
So, the multiplicative inverse of 27 in Z40 is -6.