If you need to divide 30 by 4, you get 7.5 as a result.
(For example, if you want to divide $30 among 4 persons,
every person gets $7.50). This result is called the quotient.
If you want to count only in whole dollars every person will receive $7
(Quotient is 7) and $2 remain (residue is 2).
Calculating with only whole (natural) numbers, not with fractions or decimals, happens for instance in number theory. Thereby it often happens that you are not interested in the quotient, but you have to continue calculations with only the residue. If you need to work with very large numbers, then calculating a residue costs much (computer-)time.
Montgomery multiplication can accelerate such calculations. Also in calculations regarding prime numbers, modular arithmetic plays often a role, such as in the Fermat's little theorem.
On the Internet one can find information about Modular arithmetic, about the Montgomery multiplication and the Fermat's little theorem. But unfortunately that information is not always comprehensible. Sometimes explanations are given with the aid of complex mathematical formulas.
However, there seems to be a need for a simple explanation of how the Montgomery multiplication works, and how this and the Fermat's little theorem can be implemented in a simple way in a computer program.
The document Modular arithmetic and the Montgomery multiplication is an attempt to meet this need and provides information about implementation in C++.