To find the multiplicative inverse of a number using the extended Euclidean algorithm, we need to find two integers that satisfy the equation ax + by = 1, where a is the number whose inverse we want to find, and x is the multiplicative inverse.

a.

Find the multiplicative inverse of 135 mod 61:

Applying the extended Euclidean algorithm:

Step 1:
61 = 0 * 135 + 61
135 = 2 * 61 + 13

Step 2:
61 = 4 * 13 + 9
13 = 1 * 9 + 4

Step 3:
9 = 2 * 4 + 1

Step 4:
4 = 4 * 1 + 0

The last nonzero remainder is 1, and the corresponding equation is:
1 = 9 - 2 * 4

Substituting the previous remainders, we can express the equation as:
1 = 9 - 2 * (13 - 9) = 3 * 9 - 2 * 13
1 = 3 * (61 - 4 * 13) - 2 * 13 = 3 * 61 - 14 * 13

Therefore, the multiplicative inverse of 135 mod 61 is 3.

b.

Find the multiplicative inverse of 7465 mod 2464:

Applying the extended Euclidean algorithm:

Step 1:
2464 = 0 * 7465 + 2464
7465 = 3 * 2464 + 7

Step 2:
2464 = 352 * 7 + 0

Since the remainder is 0, we stop. In this case, there is no multiplicative inverse for 7465 mod 2464 because they are not coprime (their gcd is not 1).

c.

Find the multiplicative inverse of 42828 mod 6407:

Applying the extended Euclidean algorithm:

Step 1:
6407 = 1 * 42828 + 1251
42828 = 34 * 1251 + 594

Step 2:
1251 = 2 * 594 + 63
594 = 9 * 63 + 27

Step 3:
63 = 2 * 27 + 9
27 = 3 * 9 + 0

The last nonzero remainder is 9, and the corresponding equation is:
9 = 63 - 2 * 27

Substituting the previous remainders, we can express the equation as:
9 = 63 - 2 * (1251 - 2 * 594) = 5 * 594 - 2 * 1251
9 = 5 * (42828 - 34 * 1251) - 2 * 1251 = 5 * 42828 - 172 * 1251

Therefore, the multiplicative inverse of 42828 mod 6407 is 5.