News for hackers. Stuff that matters.
Re:Testing for Divisibility by 19 by cousin_it on Monday November 23, 2020 @06:02AM (#25185535)
> The result will be a smaller number which has the same mod-19 residue.

It seems to me that the procedure works only for numbers divisible by 19. If it's not divisible, the residue may change. Try 20 for example.

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.
Re:Testing for Divisibility by 19 by mjd on Monday November 23, 2020 @01:59PM (#25190276)
You are absolutely right. I have corrected the article.
Re:Testing for Divisibility by 19 by mcv on Monday November 23, 2020 @06:18AM (#25185597)
I wonder if it doubles the residue. 20 -> 2, 21 -> 4. But 18 -> 17. And 10 -> 1. So no.
Re:Testing for Divisibility by 19 by cruegge on Monday November 23, 2020 @06:51AM (#25185761)
It does double the residue, but modulo 19. 2 * 18 = 36 = 17 (mod 19) and 2 * 10 = 20 = 1 (mod 19). The reason is that the method consists essentially of two steps. (1) Subtract a suitable multiple of 19 to make the number a multiple of 10. (2) Divide by 10. And dividing by 10 is the same as multiplying by 2, since 2 * 10 = 20 = 1 (mod 19).
Re:Testing for Divisibility by 19 by MauranKilom on Monday November 23, 2020 @06:49AM (#25185737)
Well, it does double the residue:

20 * 2 === 40 === 2 (mod 19)

21 * 2 === 42 === 4 (mod 19)

18 * 2 === 36 === 17 (mod 19), equivalently -1 * 2 === -2 === 17 (mod 19)

10 * 2 === 20 === 1 (mod 19), equivalently -9 * 2 === -18 === 1 (mod 19)