Mathematics, 18.02.2020 02:32 lauren9469

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

Answers: 2

Show answers

Answers

Answer from: blossie94681

The multiplicative inverse of a number is simply its reciprocal

The multiplicative inverse of 1234 mod 4321 is $\mathbf{ -1082 \equiv 3239\ (mod\ 4321)}$ .24140 mod 40902 as no multiplicative inverse.

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:

$\mathbf{1234 \times x \equiv 1\ (mod\ 4321)}$

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

$\mathbf{Dividend = Quotient \times Divisor + Remainder}$

So, we have:

$\mathbf{4321 = 1234 \times 3 + 619}$

Express 1234 using the above format

$\mathbf{1234 = 619 \times 1 + 615}$

Repeat the process for all quotient

$\mathbf{619 = 615 \times 1 + 4}$

$\mathbf{615 = 4 \times 153 + 3}$

$\mathbf{4= 3 \times 1 + 1}$

Next, we reverse the process as follows:

Make 1 the subject in $\mathbf{4= 3 \times 1 + 1}$

$\mathbf{1 = 4 - 3}$

Substitute an equivalent expression for 3

$\mathbf{1 = 4 - (615 - 4 \times 153)}$

$\mathbf{1 = 4 - 615 + 4 \times 153}$

Collect like terms

$\mathbf{1 = 4 + 4 \times 153 - 615 }$

$\mathbf{1 = 4 \times 154 - 615 }$

Substitute an equivalent expression for 615

$\mathbf{1 = 619 \times 154 - 155 \times (1234 - 619) }$

$\mathbf{1 = 619 \times 309 - 155 \times 1234 }$

Substitute an equivalent expression for 619

$\mathbf{1 =(4321 - 1234 \times 3) \times 309 - 155 \times 1234}$

$\mathbf{1 = 4321 \times 309 - 1082 \times 1234}$

Recall that:

$\mathbf{1234 \times x \equiv 1\ (mod\ 4321)}$

So, we have:

$\mathbf{1 \equiv -1082 \times 1234\ mod(4321)}$

Add 4321 and -1082

$\mathbf{4321 -1082 = 3239}$

Hence, the required inverse is:

$\mathbf{ -1082 \equiv 3239\ (mod\ 4321)}$

(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

Answer from: oscargonzalez1991

(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.

Answer from: Quest

step-by-step explanation: i dont

Answer from: Quest

Ithink the answer is c

Other questions on the subject: Mathematics

Mathematics, 21.06.2019 20:30, natalieburnett82

Find the quotient with the restriction.

Answers: 1

continue

Mathematics, 21.06.2019 20:30, heyyyyy39

The cost for an uberi is $2.50 plus $2.00 mile. if the total for the uber ride was $32.50, how many miles did the customer travel?

Answers: 3

continue

Mathematics, 21.06.2019 21:10, summer5716

Lines b and c are parallel. what is the measure of 2? m2 = 31° m2 = 50° m2 = 120° m2 = 130°

Answers: 2

continue

Mathematics, 21.06.2019 22:10, willisanthony7815

Acompany manufactures three types of cabinets. it makes 110 cabinets each week. in the first week, the sum of the number of type-1 cabinets and twice the number of type-2 cabinets produced was 10 more than the number of type-3 cabinets produced. the next week, the number of type-1 cabinets produced was three times more than in the first week, no type-2 cabinets were produced, and the number of type-3 cabinets produced was the same as in the previous week.

Answers: 1

continue

You know the right answer?

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