Shave off Last Two

Related wiki: Divisibility Rules > Finding Divisibility Rules

Let $x$ be the number you get by clipping off the last two digits of $n$ , and let $y$ be the number from those two digits. Then if $p$ divides $n$ , with $n = 100 \ x + y$ , $p$ should also divide $x + k \ y$ , with $k$ being the negative integer we're looking for. This results in two congruence equations:

$100 \ x + y \equiv 0 \pmod{p}$

$x + k \ y \equiv 0 \pmod{p}$

Or:

$y \ (1 - 100 \ k) \equiv \pmod{p}$

Since $p$ doesn't divide $y$ in general, it should divide $1 - 100 \ k$ :

$100 \ k \equiv 1 \pmod{p}$

This equation reads as follows: find such $k$ that dividing $100 \ k$ by $p$ leaves unit remainder. With $p = 43$ , $k = 40$ (which means adding $40 \ y$ to $x$ ), or $k = 40 - 43 = -3$ (which means subtracting $3 \ y$ from $x$ ). With $p = 67$ , $k = -2$ , so the answer to the problem is $3 \cdot 2 = 6$ .

Finding $k$ means finding modular inverse of $100$ modulo $p$ . One can use extended Euclidean algorithm for that, but for small values the result can also be found readily by hand.