Question

D. Find the multiplicative inverse of 5 mod 13

e. Use Fermat's little theorem to solve X ^ 103 = 4 (mod 11
f. Solve the following congruences (you must justify all steps)
x =6(mod 11)
x =13(mod 16)
x =9(mod 21)
x = 19 (mod 25)

Answer 1

To find the multiplicative inverse of 5 mod 13, we need to find a number x such that (5 * x) % 13 = 1. Using Fermat's little theorem, we can find that X ^ 103 is congruent to 1 (mod 11). To solve the system of congruences x = 6 (mod 11), x = 13 (mod 16), x = 9 (mod 21), x = 19 (mod 25), we can use the Chinese remainder theorem.Therefore, the solution to the system of congruences is x = 6578 (mod 8400).

Step-by-step explanation:

To find the multiplicative inverse of 5 mod 13, we need to find a number x such that (5 * x) % 13 = 1. By inspection, we find that 8 is the multiplicative inverse of 5 mod 13 because (5 * 8) % 13 = 40 % 13 = 1. Therefore, the multiplicative inverse of 5 mod 13 is 8.

To solve X ^ 103 = 4 (mod 11) using Fermat's little theorem, we need to find the modular exponentiation of 4^(11-2) % 11. By simplifying the expression, we get 4^9 % 11 = 1. Therefore, X ^ 103 is congruent to 1 (mod 11).

To solve the system of congruences x = 6 (mod 11), x = 13 (mod 16), x = 9 (mod 21), x = 19 (mod 25), we can use the Chinese remainder theorem. By applying the Chinese remainder theorem, we find that x is congruent to 6578 (mod 8400). Therefore, the solution to the system of congruences is x = 6578 (mod 8400).