Respuesta :
Answer:
(a)1≡47 mod 61
(b)1≡2329 mod 2464
(c)Does not exist
Step-by-step explanation:
The operation a(mod b) has an inverse if the the two integers (a,b)
are co-prime. i.e. their g.c.d is 1.
(a)Given 135 mod 61
We first reduce it to its lowest form.
135 mod 61=13 mod 61
61=13(4)+9 ==> 9=61-13(4)
13=9(1)+4 ==> 4=13-9(1)
9=4(2)+1 ==> 1=9-4(2)
4=1(4)
Next we rewrite 1 as a linear combination of 13 and 61.
1=9-4(2)
=9-(13-9(1))2
=9(3)-13(2)
=(61-13(4))(3)-13(2)
=61(3)-13(12)-13(2)
1=61(3)-13(14)
1=61(3)+13(-14)
1≡-14 mod 61≡(-14+61)mod 61
1≡47 mod 61
(b)7465 mod 2464
Reducing it to its lowest form
7465 mod 2464=73 mod 2464
2464=73(33)+55 ==>55=2464-73(33)
73= 55(1)+18 ==> 18=73-55(1)
55=18(3)+1 ==>1=55-18(3)
18=1(18)
Rewriting 1 as a linear combination of 73 and 2464.
1=55-18(3)
=2464-73(33)-(73-55(1))(3)
=2464-73(33)-73(3)+55(3)
=2464-73(36)+55(3)
=2464-73(36)+(2464-73(33))(3)
=2464-73(36)+2464(3)-73(99)
=2464(4)-73(135)
1=2464(4)+73(-135)
Therefore:
1≡-135 mod 2464
1≡(-135+2464)mod 2464
1≡2329 mod 2464
(c)42828 mod 6407
The two numbers are not co-prime. In fact their g.c.d is 43.
Therefore their inverse does not exist.
Answer:
The multiplicative inverse of
- A) 135 mod 61 = [tex]135^{-1} = 17[/tex]
- B) 7465 mod 2464 = [tex]7465^{-1} = 2329[/tex]
- C) 42828 mod 6407 = [tex]inverse does not exist[/tex]
Step-by-step explanation:
A)
[tex]135 = 61 * 2 + 13\\\\61 = 13 * 4 + 9\\\\13 = 9 * 1 + 4\\\\1 = 9 -4 * 2\\\\= 9 - (13-9) * 2\\\\= 3 * 9 - 13 *2\\\\= 3 * (61-13*4) - 13 * 2\\\\= 3 * 61 - 14 * 13\\\\= 3 * 61 - 14 * (135-61*2)\\\\= 31 * 61 - 14 * 135\\\\ therefore, \\\\1 = 31*61-14*135\\\\1 = -14*135\\\\1 = 17*135\\\\135^{-1} = 17[/tex]
B)
[tex]7465 = 2464*3+73\\\\2464 = 73*33+55\\\\73 = 55*1+18\\\\55 = 18*3+1\\\\1 = 55-18*3\\\\1 = 55-(73-55)*3\\\\1 = 4*55-73*3\\\\1 = 4*(2464-73*33)-73*3\\\\1 = 4*2464-135*73\\\\1 = 4*2464-135*(7465-2464*3)\\\\1 = 4*2464-135*7465+135*2464*3\\\\1 = 2464*(4+135*3)-135*7465\\\\1 = -135*7465\\\\1 = 2329*7465\\\\7465^{-1} = 2329[/tex]
C) [tex]42828 = 6*6407+4386\\\\6407 = 1*4386+2021\\\\4386 = 2*2021+344\\\\2021 = 5*344+301\\\\344 = 301*1+43\\\\301 = 7*43+0[/tex]
inverse does not exist
