3 ms·

> 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

• mcv 6y ago
  I wonder if it doubles the residue. 20 -> 2, 21 -> 4. But 18 -> 17. And 10 -> 1. So no.
  • MauranKilom 6y ago
    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)
  • cruegge 6y ago
    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).
• im3w1l 6y ago
  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.
• mjd 6y ago
  You are absolutely right. I have corrected the article.