AI Tutor
Back to Discrete Math for Shockers

Multiplicative Inverses

Solving ax congruent to 1 modulo m inside the integers, the coprimality condition deciding when such an inverse exists, and how to compute it.

Discrete Math for Shockers, Multiplicative Inverses

Status
FlagsLoading your progress…

4 exercises

Exercise 1

Solve the congruence:

  1. 3x+4≡7(mod8)3x + 4 \equiv 7 \pmod 8
  2. 9x≡4(mod22)9x \equiv 4 \pmod{22}
  3. 5x+14≡0(mod26)5x + 14 \equiv 0 \pmod{26}
2.5

Exercise 2

Find all solutions to the congruence (there could be more than one):

  1. 3x≡6(mod9)3x \equiv6 \pmod 9
  2. 4x≡3(mod8)4x \equiv 3 \pmod 8
2.5

Exercise 3

Solve the following congruences. If none exists, explain why. If there are one or more solutions, give a complete list of solution(s).

  1. 3x−4=15(mod26)3x - 4 = 15 \pmod{26}
  2. 13x−3=4(mod26)13 x - 3 = 4 \pmod{26}
  3. 8x=16(mod426)8x=16\pmod{426}
  4. 8x=16(mod425)8x=16\pmod{425}
  5. 8x=21(mod426)8x=21\pmod{426}
2.5

Exercise 4

Play around with making multiplication tables of various moduli in the Sage code in example.

  1. What condition is required for a number aa to have an inverse modulo nn?
  2. What is a condition on nn for every element to have an inverse modulo nn?
  3. If there are more than one solution to ax=b(modn)ax = b\pmod{n}, what is the relationship between each solution?
2.5

Adapted from Discrete Math for Shockers © 2021 John Hammond. Licensed under CC BY-SA 4.0. Source: Discrete Math for Shockers. Imported at revision 2538beb.