Если a = b (mod n) и с = d (mod n), то a + c = b + d (mod n) a * c = b * d (mod n) Отношения сравнения
Признак Паскаля основание системы счистления = n число для которого вычисляется признак делимости = m тогда: r1 = n mod m r2 = n * r1 mod m r3 = n * r2 mod m .... r{i} = n * r{i-1} mod m так как остатков конечное число то рано или поздно процесс закончиться. Число A = n^i * a{i} + ... + n^2 * a{2} + n * a{1} + a{0} имеет тот же остаток от деления что и r{i} * a{i} + ... + r2 * a{2} + r1 * a{1} + a{0} Признак Паскаля
общии признаки: n^i mod (n-1) = 1 n^i mod (n+1) = (-1)^i -------------------------------------------------------------------- делитель делитель делитель n n n-1 n-1 n+1 n+1 -------------------------------------------------------------------- 2 - - - 3 - 3 - 2 - 4 2 4 2 3 - 5 - 5 - 4 2 6 2,3 6 2,3 5 - 7 - 7 - 6 2,3 8 2,4 8 4,2 7 - 9 3 9 3 8 2,4 10 2,5 10 2,5 9 3 11 - 11 - 10 2,5 12 2,3,4 12 2,3,4 11 - 13 - 13 - 12 2,3,4 14 2,7 14 2,7 13 - 15 3,5 15 3,5 14 2,7 16 2,4,8 16 2,4,8 15 3,5 17 - -------------------------------------------------------------------- на n-1: r0 = 1 r1 = n mod n-1 = 1 сумма цифр числа тоже самое для его делителей (если есть) на n+1: r0 = 1 r1 = n mod n+1 = -1 r2 = -n mod n+1 = 1 чередование Признаки делимости можно использовать для быстрого получения остатков от деления. Особенно важно вычисление остатков от деления для перевода в RNS.
Признаки делимости в десятичной системе счисления: на 2: число четно на 3: сумма цифр числа делиться на 3 на 4: число образованное последними двумя цифрами исходного числа делиться на 4 на 5: последняя цифра числа: 0 или 5 на 6: делиться на 2 и 3 на 7: число без последней цифры минус удвоенная последняя цифра делиться на 7. 371: 37 - 2 * 1 = 35 : 3 - 5 * 2 = -7 на 8: число образованное последними тремя цифрами исходного числа делиться на 8 на 9: сумма цифр числа делиться на 9 на 10: последняя цифра числа: 0 на 11: сумма цифр числа с чередующимися знаками делиться на 11 182919: + 1 - 8 + 2 - 9 + 1 - 9 = -22 на 12: делиться на 3 и 4 на 13: число десятков + учетверенное число единиц кратно 13 845: 84 + 4 * 5 = 104: 10 + 4 * 4 = 26 на 14: делиться на 2 и 7 на 15: делиться на 3 и 5 Для десятичной системы: на 2: r0 = 1 r1 = 10 mod 2 = 0 1 цифра на 3: r0 = 1 r1 = 10 mod 3 = 1 сумма цифр на 4: r0 = 1 r1 = 10 mod 4 = 2 r2 = 20 mod 4 = 0 2 цифры на 5: r0 = 1 r1 = 10 mod 5 = 0 1 цифра на 6: r0 = 1 r1 = 10 mod 6 = 4 r2 = 40 mod 6 = 4 составное на 7: r0 = 1 r1 = 10 mod 7 = 3 r2 = 30 mod 7 = 2 r3 = 20 mod 7 = 6 // -1 r4 = 60 mod 7 = 4 // -3 r5 = 40 mod 7 = 5 * // -2 r6 = 50 mod 7 = 1 * на 8: r0 = 1 r1 = 10 mod 8 = 2 r2 = 20 mod 8 = 4 r3 = 40 mod 8 = 0 3 цифры на 9: r0 = 1 r1 = 10 mod 9 = 1 сумма цифр на 10: r0 = 1 r1 = 10 mod 10 = 0 1 цифра на 11: r0 = 1 r1 = 10 mod 11 = -1 .... чередование со знаками на 12: r0 = 1 r1 = 10 mod 12 = 10 r2 = 100 mod 12 = 4 r3 = 40 mod 12 = 4 составное на 13: r0 = 1 r1 = 10 mod 13 = 10 r2 = 100 mod 13 = 9 r3 = 90 mod 13 = 12 r4 = 120 mod 13 = 3 r5 = 30 mod 13 = 4 * r6 = 40 mod 13 = 1 * на 14: r0 = 1 r1 = 10 mod 14 = 10 r2 = 100 mod 14 = 2 r3 = 20 mod 14 = 6 r4 = 60 mod 14 = 4 r5 = 40 mod 14 = 12 //-2 r6 = 120 mod 14 = 8 //-6 r7 = 80 mod 14 = 10 //-4 на 16: r0 = 1 r1 = 10 mod 16 = 10 r2 = 100 mod 16 = 4 r3 = 40 mod 16 = 8 r4 = 80 mod 16 = 0 4 цифры на 17: r0 = 1 r1 = 10 mod 17 = 10 r2 = 100 mod 17 = 15 r3 = 150 mod 17 = 14 r4 = 140 mod 17 = 4 r5 = 40 mod 17 = 6 r6 = 60 mod 17 = 9 r7 = 90 mod 17 = 5 r8 = 50 mod 17 = 16 r9 = 160 mod 17 = 7 r10 = 70 mod 17 = 2 r11 = 20 mod 17 = 3 r12 = 30 mod 17 = 13 r13 = 130 mod 17 = 11 r14 = 110 mod 17 = 8 r15 = 80 mod 17 = 12 * r16 = 120 mod 17 = 1 * 10
Таблица умножения 11 12 13 14 15 16 17 18 19 20 21 2 22 24 26 28 30 32 34 36 38 40 42 3 33 36 39 42 45 48 51 54 57 60 63 4 44 48 52 56 60 64 68 72 76 80 84 5 55 60 65 70 75 80 85 90 95 100 105 6 66 72 78 84 90 96 102 108 114 120 126 7 77 84 91 98 105 112 119 126 133 140 147 8 88 96 104 112 120 128 136 144 152 160 168 9 99 108 117 126 135 144 153 162 171 180 189 10 110 120 130 140 150 160 170 180 190 200 210 11 121 132 143 154 165 176 187 198 209 220 231 12 132 144 156 168 180 192 204 216 228 240 252 13 143 156 169 182 195 208 221 234 247 260 273 14 154 168 182 196 210 224 238 252 266 280 294 15 165 180 195 210 225 240 255 270 285 300 315 16 176 192 208 224 240 256 272 288 304 320 336 17 187 204 221 238 255 272 289 306 323 340 357 18 198 216 234 252 270 288 306 324 342 360 378 19 209 228 247 266 285 304 323 342 361 380 399 20 400 420
Троичная система: на 2: сумма цифр делиться на 2 на 3: последняя цифра 0 на 4: чередование r0 = 1 r1 = 3 mod 4 = 3 // -1 r2 = 3*3 mod 4 = 1 на 5: r0 = 1 r1 = 3 mod 5 = 3 // -2 r2 = 3*3 mod 5 = 4 // -1 r3 = 3*4 mod 5 = 2 * r4 = 3*2 mod 5 = 1 * 3
Шестнадцитеричная система: на 2: четное на 3: сумма цифр делиться на 3 на 5: сумма цифр делиться на 5 на 6: делиться на 2 и 3 на 8: последняя цифра 0 или 8 на A: четное + сумма цифр делиться на 5 на F: сумма цифр делиться на F на 7: r0 = 1 r1 = 16 mod 7 = 2 r2 = 16*2 mod 7 = 32 mod 7 = 4 r3 = 16*4 mod 7 = 64 mod 7 = 1 на 9: r0 = 1 r1 = 16 mod 9 = 7 r2 = 16*7 mod 9 = 112 mod 9 = 22 mod 9 = 4 r3 = 16*4 mod 9 = 64 mod 9 = 1 16