Find the following multiplicative inverses: (1) 23^-1 (mod 26) (2) 5^-1 (mod 13)

Question

Find the following multiplicative inverses: (1) 23^-1 (mod 26) (2) 5^-1 (mod 13) (3) 3^-1(mod 8) (4) 79 ^-1(mod 80) Ex #2. Let n he a positive integer. Explain why (n - 1)^-1 is congruent to n - 1 (mod n). Ex #3. We will call treven an integer that is divisible by 3 with no remainder. An integer that is not treven will be called trodd. Show that the sum of trevens is treven; and that the sum of a treven and a trodd is trodd. What about the sum of two trodds? Make a conjecture and prove it. Ex # 5. You have intercepted the following ciphertext: KESC GTHG XOGKWH L SWH WPGCQTU. You know that the message was created with an affine cipher that transforms T into H and transforms 0 into E. Find (1) the encipherment formula f(x), (2) the decipherment formula g(x), and (3) the original message.

Explanation / Answer

The answers:

1) Multiplicative inverses.

i) 23^-1 mod 26 = 3 mod 26.

ii) 5^-1 mod 13 = 3 mod 13

iii) 3^-1 mod 8 = 2 mod 8

iv) 79^-1 mod 80 = 1 mod 80

2) We have to prove (n-1) ^ (-1) = (n-1) mod n

Taking n-1 to the other side

which is equivalent to 1 = (n-1)^2 mod n

It will suffice to prove LHS = RHS

(n-1)^ 2= n^2 -2 n + 1 mod n = 1 mod n (as n^2 and 2 n are divisble by n)

Hence proved.

3) All trevens can be represented as 3 * k (where k belongs to 1,2,3,..)

All trodds can be either 3*k +1 / 3*k +2

Treven + treven = 3k + 3m = 3l which is a treven. Hence treven + treven = treven

Treven + Trodd = 3K + 3m +1(or)2 = 3l +1(or)2 which is a trodd

Trodd + Trodd Gives 4 cases

case 1/case2 : 3k + 1 + 3 m +1 = 3l + 2 trodd

case 3/case4 : 3k + 1 + 3m + 2 = 3l treven

We cannot state with 100% certainity which is which.

5) Affine cipher in which T -> h and O -> E

If the cipher => ax + b

then 20a+b mod 26 = 8          ---------------------------1

and 15a+b mod 26 = 5           ---------------------------2

Using 1 &2,

5a mod 26 = 3

minimum value of a = 11; and hence 15a + b mod 26 = 5 => b-1 mod 26 => b=6

Hence encipherment formula f(x) = 11x +6=11x+6

Decipherment forumla g(x) => x-6* (11)^-1 mod 26

original message; deciphering using forumla => You Cant Always Trust Spacing

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.