-11

I am reading a text on Data Mining. Given the problem: enter image description here

How do we determine that the inverse of 11 is 120?

Bill Dubuque
  • 272,048
Evan Gertis
  • 166
  • 1
  • 7
  • 6
    The inverse of $11$ mod $120$ is $11$ for exactly the reasons described at the beginning of the second paragraph. You should explain precisely what about their explanation doesn’t make sense – FShrike Aug 26 '22 at 20:21
  • 4
    Note also that the text probably means $q=13$. – Toffomat Aug 26 '22 at 20:27
  • 1
    It's not desirable to post an image of a passage unless the problem is about the appearance of the text, e.g. an unfamiliar piece of notation. In addition a better way of identifying the passage than "a text on Data Mining" would be useful to Readers. Cite the title, author, etc. – hardmath Aug 26 '22 at 21:03
  • 3
    You misinterpreted the text, which did not say that the inverse of 11 is 120. Going forward, please proofread your MathSE postings. – user2661923 Aug 26 '22 at 21:24
  • 3
    See Solving linear congruences by hand: modular fractions and inverses and its links for most all known methods to compute modular inverses - with hundreds of worked examples. Please search for answers before posting questions. – Bill Dubuque Aug 26 '22 at 21:46

1 Answers1

-1

We want to solve $11x \equiv 1 \pmod{120}$ for $x$.

So by Euclidean algorithm,

$120 = 11*10 + 10 \\ 11 = 10*1 + 1 \\ 10 = 1*10 + 0$

Now using the above and doing some substitutions we express $1$ as a linear combination of $120$ and $11$,

$1 = 11 - 10*1 = 11 - (120 - 11*10)*1 = 11*11 - 120*1$

Then by definition of congruence modulo $120$ we have,

$11*11 - 120*1 = 1 \implies 11*11 = 1 + 120*1 \implies 11*11 \equiv 1 \pmod{120}$

Therefore, $x = 11$ satisfies the given equation above.

What do you need to know to find inverses like I did above?

  1. Euclidean algorithm.
  2. For all integers $a, b$, not both zero, if $d = \gcd(a, b)$, then there exist integers $s, t$ such that $as + bt = d$.
  3. For all integers $a, n$, if $\gcd(a, n) = 1$, then there exists an integer $s$ such that $as \equiv 1 \pmod n$, and so $s$ is an inverse for $a$ modulo $n$.

Of course, you also must know the definitions of divisibility, greatest common divisor, congruence modulo bla and Euclid's division lemma. You can learn all that from any elementary number theory or discrete math textbook.

user1033615
  • 70