I might start with deducing some theorems about modular addition and multiplication.
[MATH]\text {THEOREM I: } c = a \text { mod}(b) \iff \exists \text { non-negative integer } \text d \text { such that } a = bd + c.[/MATH]
Proof
[MATH]c = a \text { mod}(b) \implies c = a - \left ( b * \left \lfloor \dfrac{a}{b} \right \rfloor \right ) \text { by definition.}[/MATH]
[MATH]\text {Let } d = \left ( \left \lfloor \dfrac{a}{b} \right \rfloor \right ) \implies[/MATH]
[MATH]d \ge 0 \ \because \ a > 0 < b \text { and } d \text { is an integer by definition of floor function.}[/MATH]
[MATH]\therefore c = a - bd \implies a = bd + c. \text {Q.E.D.}[/MATH]
I'll let you figure out how to do the second half of that theorem.
[MATH]\text {THEOREM II: } c = a \text { mod}(b) \text { and } p = q \text { mod}(b) \implies (a * q) \text { mod}(b) = (c * p) \text { mod}(b).[/MATH]
Proof
[MATH]\text {By Theorem I, } \exists \text { integer } d \text { such that } a = bd + c \text { and integer } r \text { such that } q = br + p.[/MATH]
[MATH]\text {By definition, } (a * q) \text{ mod}(b) = (a * q) - \left ( b * \left \lfloor \dfrac{a * q}{b} \right \rfloor \right ) =[/MATH]
[MATH]\{(bd + c)(br + p) - \left ( b * \left \lfloor \dfrac{(bd + c)(br + q)}{b} \right \rfloor \right ) =[/MATH]
[MATH]b^2dr + bdp + bcr + cp - \left ( b * \left \lfloor \dfrac{b^2dr + bdp + bcr + cp}{b} \right \rfloor \right) =[/MATH]
[MATH]b^2dr + bdp + bcr + cp - \left ( b * \left \lfloor bdr + dp + cr + \dfrac{cp}{b} \right \rfloor \right ).[/MATH]
[MATH]\text {But } b, \ c,\ d,\ p, \text { and } r \text { are all integers} \implies[/MATH]
[MATH](a * q) \text{ mod}(b) = b^2dr + bdp + bcr + cp - b(bdr + dp + cr) -\left (b * \left \lfloor \dfrac{cp}{b} \right \rfloor \right ).[/MATH]
[MATH]\therefore (a * q) \text{ mod}(b) = (c * p) - \left ( b * \left \lfloor \dfrac{(c * p)}{b} \right \rfloor \right ) = (c * p) \text{ mod}(b) \text { by definition. Q.E.D.}[/MATH]
Now I'd think about induction for powers.
[MATH]\text {THEOREM I: } c = a \text { mod}(b) \iff \exists \text { non-negative integer } \text d \text { such that } a = bd + c.[/MATH]
Proof
[MATH]c = a \text { mod}(b) \implies c = a - \left ( b * \left \lfloor \dfrac{a}{b} \right \rfloor \right ) \text { by definition.}[/MATH]
[MATH]\text {Let } d = \left ( \left \lfloor \dfrac{a}{b} \right \rfloor \right ) \implies[/MATH]
[MATH]d \ge 0 \ \because \ a > 0 < b \text { and } d \text { is an integer by definition of floor function.}[/MATH]
[MATH]\therefore c = a - bd \implies a = bd + c. \text {Q.E.D.}[/MATH]
I'll let you figure out how to do the second half of that theorem.
[MATH]\text {THEOREM II: } c = a \text { mod}(b) \text { and } p = q \text { mod}(b) \implies (a * q) \text { mod}(b) = (c * p) \text { mod}(b).[/MATH]
Proof
[MATH]\text {By Theorem I, } \exists \text { integer } d \text { such that } a = bd + c \text { and integer } r \text { such that } q = br + p.[/MATH]
[MATH]\text {By definition, } (a * q) \text{ mod}(b) = (a * q) - \left ( b * \left \lfloor \dfrac{a * q}{b} \right \rfloor \right ) =[/MATH]
[MATH]\{(bd + c)(br + p) - \left ( b * \left \lfloor \dfrac{(bd + c)(br + q)}{b} \right \rfloor \right ) =[/MATH]
[MATH]b^2dr + bdp + bcr + cp - \left ( b * \left \lfloor \dfrac{b^2dr + bdp + bcr + cp}{b} \right \rfloor \right) =[/MATH]
[MATH]b^2dr + bdp + bcr + cp - \left ( b * \left \lfloor bdr + dp + cr + \dfrac{cp}{b} \right \rfloor \right ).[/MATH]
[MATH]\text {But } b, \ c,\ d,\ p, \text { and } r \text { are all integers} \implies[/MATH]
[MATH](a * q) \text{ mod}(b) = b^2dr + bdp + bcr + cp - b(bdr + dp + cr) -\left (b * \left \lfloor \dfrac{cp}{b} \right \rfloor \right ).[/MATH]
[MATH]\therefore (a * q) \text{ mod}(b) = (c * p) - \left ( b * \left \lfloor \dfrac{(c * p)}{b} \right \rfloor \right ) = (c * p) \text{ mod}(b) \text { by definition. Q.E.D.}[/MATH]
Now I'd think about induction for powers.
Last edited:
