# How are these operations the same? How to convert a multiplication in a different form?

I am reading on a specific operation, how it should be done in order to avoid overflow during multiplication.
The operation is:
$$( A * \text{state} ) \% M;$$

This is susceptible to overflow.

The modified operation that does not have this pitfall is:
$$A(\text{state}(\bmod{Q})) - R(\text{state}/Q) + M\delta(\text{state})$$

$Q$ and $R$ are the quotient and remainder of $M/A$.

$\delta$ evaluates to 0 or 1 depending on the subtraction of the first 2 terms.

This $R (\text{state}/Q)$ is low limit/bound but I don't know the tag.

I don't get how these expressions are equivalent i.e. produce the same result.

Could you please help me?

-
Are you sure it is the quotient and remainder of $M/A$ and not of $A/M$? –  Arturo Magidin Apr 3 '12 at 16:51
Looks quite like the Schrage multiplication trick... –  Ｊ. Ｍ. Apr 3 '12 at 16:54
@ArturoMagidin:It says M/A unless it is a typo.Also that R<Q must be true to not have overflow –  user384706 Apr 3 '12 at 16:54
@JM:What is Schrage trick? –  user384706 Apr 3 '12 at 16:55
I guess Schrage's multiplication algorithm: PDF here, here. –  user2468 Apr 3 '12 at 16:57