How does Montgomery reduction work?
In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier.

Peter L. Montgomery; Modular multiplication without trial division ,1985

We need the modulus $n$ we are working and an integer $r$ such that $\gcd(r,n) =1$ and $r&gt;n$
Definition: The Montgomery representation of $x \in [0,n-1]$ is $\bar{x} = (xr) \bmod n$
Definition: The Montgomery reduction of $u \in [0,rn-1]$ is $Redc(u) = (ur^{-1}) \bmod n$. This is also called $n$-residue with respect to $r$. Indeed, one can show that this set $$\{i\cdot r \bmod n | 0 \leq i \leq n\}$$ is a complete residue system.
In Cryptography, we usually work with prime modulus therefore we can chose $r = 2^k$. In this case the  $\gcd(r,n) = \gcd(2^k,n) = 1$ is satisfied.

Fact 1 :

Since we are working modulo $n$, this is an elementary result.

Fact 2: If $x$ is even, then performing a division by two in $\mathbb{Z}$ is congruent to $x\cdot 2^{−1} \bmod n$. Actually, this is an application of the fact that if $x$ is evenly divisible by any $k \in \mathbb{Z}$, then division in $\mathbb{Z}$ will be congruent to multiplication by $k^{−1} \bmod n$.

What they try to say is

Let $k$ divides $x$ then $u \cdot k = x$ take the modulus $n$ on both sides.  $$u \cdot k = x \bmod n$$ Since $n$ is prime than $k^{-1}$ exist in modulo $n$ and that can be found with the Extended Euclidean Algorithm. For Montgomery this is required only once for $r$. Now we have;

$$u \cdot k \cdot k^{-1} = x \cdot k^{-1} \bmod n$$
$$u = x \cdot k^{-1} \bmod n$$

1.2 x &lt;- x/2

When the $r = 2^k$ this is usually performed by shift operations. This is a trick of the Montgomery. The trial division is transferred into shifts.
x = x &gt;&gt; 2


What are the solid principles behind Montgomery multiplication with reduction?

Montgomery Reduction This is the Wikipedia version.
input: Integers r and n with gcd(r, n) = 1,
       Integer n′ in [0, r − 1] such that nn′ ≡ −1 mod r,
       Integer T in the range [0, rn − 1]
output: Integer s in the range [0, n − 1] such that s ≡ Tr^−1 mod n

m = ((T mod r)n′) mod r
t = (T + mn) / r
if t ≥ n then
    return t − n
else
    return t

Now, the advantage is clear. Since $r= 2^{k}$ the division and $\bmod$ operations are cheap by shifting or masking.
The $n'$ is defined as  $rr^{-1} -n n' =1$
The correctness can be seen by

observe that if $m = (( T \bmod r )n^{'}) \bmod r$ then $T + mn$ is divisible by $r$.

$$T + mn \equiv T + (((T \bmod r)n') \bmod r)n \equiv T + T n' n \equiv T - T \equiv 0 \pmod{R}$$ There for the $t$ is integer, not a floating point.
The output then is either $y$ or $t-n$ ( remember the fact 1). Now let see why the output is $Tr^{-1}$. We again use what we know
$$t \equiv ( T + mn )r^{-1} \equiv Tr^{-1} + (mr^{-1})n \equiv Tr^{-1} \pmod{n)}$$
Therefore the output has the correct residue as we wanted.
Why the substruction? We need to keep track of the $t$'s size.

$m \in [0,r-1]$
$T+mn$ then lies between $0$ and $(rn-1) + (r-1)n &lt; 2rn$. Since the divived by $r$ then $0 \leq t \leq 2n-1$. A single substraction can reduce the $t$ into the desired range.

Montgomery Product
We are going to define a function that is going to be very powerful. Remember $\bar{a} = ar \bmod n$

$MonPro(\bar{a},\bar{b},r,n)$
//outputs $t = MonPro(\bar{a},\bar{b},r,n) = \bar{a}\bar{b}r^{-1} \pmod{n}$

$ T = \bar{a}\bar{b}$
$m = T n' \bmod r$
$t = (T+mn)/r$
if $t \geq n$ $\text{return}(t-n)$
$\text{return}(t)$



Let us simplify the $MonPro(\bar{a},\bar{b},r,n)$ to $MonPro(\bar{a},\bar{b})$ since we keep them constant and $r^{}$ can be calculated as constant before the operations.

What will happen if we call : $MonPro(\bar{a},1)$?

$$MonPro(\bar{a},1) = (a r) \cdot 1 \cdot r^{-1} = a \pmod{n}$$

What will happen if we call : $MonPro(\bar{a},b)$?

$$MonPro(\bar{a},b) = (a r) \cdot b \cdot r^{-1} = a \cdot b\pmod{n}$$

What will happen if we call : $MonPro(a,r)$?

$$MonPro(a,1) = a \cdot 1 \cdot r^{-1} = a r^{-1} \pmod{n}$$