Give a number $x$ such that $139x + 1$ is divisible by 1111

Question

Give a number $x$ such that $139x + 1$ is divisible by 1111.

So this is a question of my abstract algebra homework, but not sure how to get started. I thought of doing something with $139x = -1$ mod $1111$, but the solution says: $x=-139^{-1} \in (\mathbb{Z}/1111\mathbb{Z})^{*}$. However I have no idea where $-139^{-1}$ is coming from... They conclude this numbers equals 1103, but without any explanation. Maybe someone could clarify this? Thanks in advance.

Answer 1

By trial and error, the solution $x=8$ of $$139x\equiv 1\mod 1111$$ can relatively easy been detected. This menas that $x=-8\equiv 1103\mod 1111$ solves $$139x\equiv -1\mod 1111$$ Using the chinese remainder theorem, the numbers get somewhat smaller, making the solutions slightly easier.

Answer 2

Let's see. All congruence are $\bmod 1111$.

$139x\equiv -1$

Divide $1111$ by $139$, quotient = $7$, remainder =$138$. Multiply by one more than the quotient, thus $×8$:

$1112x \equiv 1x \equiv -8$

So $x\equiv -8 \bmod 1111$ making $1103$ the smallest positive solution.