News for hackers. Stuff that matters.
Re:Testing for Divisibility by 19 by im3w1l on Monday November 23, 2020 @09:36AM (#25187124)
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.

There are no comments on this comment yet.