(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 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:
[tex]\mathbf{1234 \times x \equiv 1\ (mod\ 4321)}[/tex]
When the extended Euclidean's algorithm is applied, we start by writing the expression in the following format:
[tex]\mathbf{Dividend = Quotient \times Divisor + Remainder}[/tex]
So, we have:
[tex]\mathbf{4321 = 1234 \times 3 + 619}[/tex]
Express 1234 using the above format
[tex]\mathbf{1234 = 619 \times 1 + 615}[/tex]
Repeat the process for all quotient
[tex]\mathbf{619 = 615 \times 1 + 4}[/tex]
[tex]\mathbf{615 = 4 \times 153 + 3}[/tex]
[tex]\mathbf{4= 3 \times 1 + 1}[/tex]
Next, we reverse the process as follows:
Make 1 the subject in [tex]\mathbf{4= 3 \times 1 + 1}[/tex]
[tex]\mathbf{1 = 4 - 3}[/tex]
Substitute an equivalent expression for 3
[tex]\mathbf{1 = 4 - (615 - 4 \times 153)}[/tex]
[tex]\mathbf{1 = 4 - 615 + 4 \times 153}[/tex]
Collect like terms
[tex]\mathbf{1 = 4 + 4 \times 153 - 615 }[/tex]
[tex]\mathbf{1 = 4 \times 154 - 615 }[/tex]
Substitute an equivalent expression for 615
[tex]\mathbf{1 = 619 \times 154 - 155 \times (1234 - 619) }[/tex]
[tex]\mathbf{1 = 619 \times 309 - 155 \times 1234 }[/tex]
Substitute an equivalent expression for 619
[tex]\mathbf{1 =(4321 - 1234 \times 3) \times 309 - 155 \times 1234}[/tex]
[tex]\mathbf{1 = 4321 \times 309 - 1082 \times 1234}[/tex]
Recall that:
[tex]\mathbf{1234 \times x \equiv 1\ (mod\ 4321)}[/tex]
So, we have:
[tex]\mathbf{1 \equiv -1082 \times 1234\ mod(4321)}[/tex]
Add 4321 and -1082
[tex]\mathbf{4321 -1082 = 3239}[/tex]
Hence, the required inverse is:
[tex]\mathbf{ -1082 \equiv 3239\ (mod\ 4321)}[/tex]
(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:
https://brainly.com/question/13715269
