Uniqueness of modular multiplicative inverse

Solution 1:

Since the mistake of the proof is discussed in the comments, I want to point out the mistake you made:

I am self studying so internet is obviously the first thing I check for any deeper insight.

WRONG. The internet is the first thing one checks for superficial insight. For deeper insight, the thing to check is textbooks (some of which might be found on the internet), and for the deepest insight, you take a class, discuss matters with fellow students, T.A.'s and professors, and ultimately use your own reasoning, e.g. by doing the exercises a good textbook contains and a good lecturer gives you.

Now of course there are good resources on the internet. But there's also ... not so good resources. Looking at your link, I would immediately have my doubts about it; but that's because I have been through a decade of university math. You're not there. Which is why I can only strongly advise you to not just rely on googling. And not on blogs of non-professional mathematicians. You know what, not on blogs at all (of course Terry Tao's blog is probably trustworthy; but don't start there).

Look, even textbooks contain mistakes. Lecture notes more so. I consider myself a good calculus teacher, but rarely a lecture passes in which I do not notice a silly mistake or unclarity in my lecture notes -- something small and silly when I spot it, but maybe it made one student "waste" 15 minutes on it. Which is why it's good for them that they can ask me, and that I can point it out in the next lesson for everyone; all resources that a self-learner does not have.

If this proof is actually wrong then reading up on such things on the internet is very inefficient. I am a beginner at number theory and that goes doubly for me as I consider such a proof to be correct at first glance and then I waste a lot of time trying to wrap my mind around an incorrect statement.

The first sentence is correct. For the second one, well if you figured out the mistake, the time is not entirely wasted.

How did the rest of you teach yourself a mathematical subject without such inefficiencies?

As said above, I first got a solid groundwork by attending university classes. Afterwards, I did self-learning when necessary by using reliable sources (textbooks if possible, more than one at a time if possible to see things from different angles and spot mistakes in one), and working through a lot of the exercises.

Solution 2:

The proof is correct, but quite roundabout (with an inconsequential $\rm\color{#c00}{error}$). Let's review it in detail.

Uniqueness of multiplicative inverse
Prove that any multiplicative inverse $i$ of $m$ modulo $n$ is unique modulo $n$.

Proof $ $ Let $i$ and $j$ be two multiplicative inverses of $m$ modulo $n\!:\,$ $\,im\equiv jm\equiv 1\pmod{\!n}.\,$ By the definition of congruence modulo $n$, $im = pn+1$ for some integer $p$, yielding the Bézout’s identify $1 = im-pn$. Since $1$ clearly divides $m$ and $n$, $\,\gcd(m,n)=1$ by the Bézout's lemma. Thus, $i\equiv j \color{#c00}{\equiv1}\pmod{\!n}$ by the cancellation law in modular arithmetic. Q.E.D.

It uses: $\,m\,$ invertible $\!\bmod n$ $\,\Rightarrow\, im-pn=1\,\Rightarrow\, \gcd(m,n)=1$ $\,\Rightarrow\,m$ is cancellable $\!\bmod m$. The middle two inferences are superflous because invertible elements are always cancellable, i.e. $\,im\equiv jm\,\overset{\large \times\, m^{-1}}\Longrightarrow\, i\equiv j.\,$ Bezout isn't needed here since we already have know an inverse $j$ of $m$ so we can replace $\,m^{-1}\,$ by $\,j\,$ in this inference, i.e. scale $\,im\equiv jm\,$ by $\,m^{-1}\equiv j\,$ to get $\,i\equiv j$.

Simpler $\:\! \ i \equiv i (mj)\equiv (im)j \equiv j.\,$ Thus $\,i\equiv j\, $ ($\color{#c00}{\rm{not}}\,\ i\equiv j\color{#c00}{\equiv 1})$ so any two inverses $\,i,j\,$ are congruent, i.e. inverses are unique $\!\bmod n.\,$ Therefore there is a unique $\,i\equiv m^{-1}$ lying in every complete set $S$ of residues $\!\bmod n,\,$ e.g. the common least natural residues $\,S = \{0,1,\ldots n\!-\!1\}$.

Remark $ $ See also this answer and its linked sci.math thread on an additive analog - the uniqueness of solutions of $\,x+a = b.\,$ The case $\,b = 0\,$ yields the uniqueness of additive inverses. As above, many students given roundabout solutions (and have difficulty understanding efficient solutions).

If this proof is actually wrong then reading up on such things on the internet is very inefficient. I am a beginner at number theory and that goes doubly for me as I consider such a proof to be correct at first glance and then I waste a lot of time trying to wrap my mind around an incorrect statement.

The quality of internet information varies widely - even in more esoteric fields such as mathematics.

How did the rest of you teach yourself a mathematical subject without such inefficiencies? I am self studying so internet is obviously the first thing I check for any deeper insight.

Start with respected textbooks or lecture notes at your level (browse the courses offered at respectable universities to see what they use). You can also find many textbook reviews on the internet.