Using the extended Euclidean algorithm, find the multiplicative inverse of a. 1234 mod 4321 b. 24140 mod 40902

The multiplicative inverse of a number is simply its reciprocal

To determine the multiplicative inverse of a mod b, one of a and b must not be an even number

(a) Multiplicative inverse of 1234 mod 4321

This can be written as:

When the extended Euclidean's algorithm is applied, we start by writing the expression in the following format:

So, we have:

Express 1234 using the above format

Repeat the process for all quotient

Next, we reverse the process as follows:

Make 1 the subject in

Substitute an equivalent expression for 3

Collect like terms

Substitute an equivalent expression for 615

Substitute an equivalent expression for 619

Recall that:

So, we have:

Add 4321 and -1082

Hence, the required inverse is:

(b) Multiplicative inverse of 24140 mod 40902

Recall that:

To determine the multiplicative inverse of a mod b, one of a and b must not be an even number

Because 24140 and 40902 are both even numbers, then:

24140 mod 40902 has no multiplicative inverse

Read more about multiplicative inverse at:

link

(a) The inverse of 1234 (mod 4321) is x such that 1234*x ≡ 1 (mod 4321). Apply Euclid's algorithm:

4321 = 1234 * 3 + 619

1234 = 619 * 1 + 615

619 = 615 * 1 + 4

615 = 4 * 153 + 3

4 = 3 * 1 + 1

Now write 1 as a linear combination of 4321 and 1234:

1 = 4 - 3

1 = 4 - (615 - 4 * 153) = 4 * 154 - 615

1 = 619 * 154 - 155 * (1234 - 619) = 619 * 309 - 155 * 1234

1 = (4321 - 1234 * 3) * 309 - 155 * 1234 = 4321 * 309 - 1082 * 1234

Reducing this leaves us with

1 ≡ -1082 * 1234 (mod 4321)

and so the inverse is

-1082 ≡ 3239 (mod 4321)

(b) Both 24140 and 40902 are even, so there GCD can't possibly be 1 and there is no inverse.

the answer is 175.4379

step-by-step explanation: