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

Hold on lemme do the work

Answer from: Quest

2.9863 to the 60th power

Another question on Mathematics

Mathematics, 21.06.2019 15:00

In which figure is de bc ? a. figure 1 b. figure 2 c. figure 3 d. figure 4

Answers: 1

Answer

Mathematics, 21.06.2019 17:20

The function a represents the cost of manufacturing product a, in hundreds of dollars, and the function b represents the cost of manufacturing product b, in hundreds of dollars. a(t) = 5t + 2 b(t) = 7t - 2t +4 find the expression that describes the total cost of manufacturing both products, a(t) + b(t). a. 7t^2 - 7t + 2 b. 7t^2 + 3 +6 c. 7t^2 + 7t - 6 d. 7t^2 - 3t + 6

Answers: 3

Answer

Mathematics, 21.06.2019 21:00

Ariana starts with 100 milligrams of a radioactive substance. the amount of the substance decreases by 20% each week for a number of weeks, w. the expression 100(1−0.2)w finds the amount of radioactive substance remaining after w weeks. which statement about this expression is true? a) it is the difference between the initial amount and the percent decrease. b) it is the difference between the initial amount and the decay factor after w weeks. c) it is the initial amount raised to the decay factor after w weeks. d) it is the product of the initial amount and the decay factor after w weeks.

Answers: 1

Answer

Mathematics, 21.06.2019 22:40

Use this graph to find the cost of 6 show tickets

Answers: 1

Answer

You know the right answer?

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

Questions