Well there are two parts to it really. Take a number say 123. Write it as 1 * 10^2 + 2 * 10 + 3. In the first step we multiply parts of this expression by 20.

Well there are two parts to it really. Take a number say 123. Write it as 1 * 10^2 + 2 * 10 + 3. In the first step we multiply parts of this expression by 20. This doesn't change the residue since 20 = 1 mod 19 1 * 10^2 + 2 * 10 + 3 1 * 10^2 + (2+3*2) * 10 1 * 10^2 + 8 * 10 (1+8*2) * 10^2 17 * 10^2 Now heres the part where we do change the residue. We note that 10 and 19 are coprime. So 17 * 10^2 is divisible by 19 if and only if 17 is. So replacing 17 * 10^2 with 17 might change residue, but wont change divisibility.