Правило делимости

Краткая формула определения, делится ли заданное число на фиксированный делитель

Правило делимости — это сокращенный и полезный способ определения, делится ли заданное целое число на фиксированный делитель без выполнения деления, обычно путем проверки его цифр. Хотя существуют тесты делимости для чисел в любой системе счисления , или основании, и все они различны, в этой статье представлены правила и примеры только для десятичных чисел, или чисел с основанием 10. Мартин Гарднер объяснил и популяризировал эти правила в своей колонке «Математические игры» в журнале Scientific American в сентябре 1962 года . ^[1]

Признаки делимости чисел от 1 до 30

Правила, приведенные ниже, преобразуют заданное число в, как правило, меньшее число, сохраняя при этом делимость на интересующий делитель. Поэтому, если не указано иное, полученное число следует оценить на делимость на тот же делитель. В некоторых случаях процесс можно повторять до тех пор, пока делимость не станет очевидной; в других случаях (например, при проверке последних n цифр) результат должен быть проверен другими способами.

Для делителей с несколькими правилами правила обычно располагаются в порядке убывания: сначала те, которые подходят для чисел с большим количеством цифр, а затем те, которые полезны для чисел с меньшим количеством цифр.

Чтобы проверить делимость числа на степень 2 или степень 5 (2 ⁿ или 5 ⁿ , где n — положительное целое число), нужно посмотреть только на последние n цифр этого числа.

Чтобы проверить делимость на любое число, выраженное как произведение простых множителей , мы можем отдельно проверить делимость на каждое простое число в его соответствующей степени. Например, проверка делимости на 24 (24 = 8×3 = 2 ³ ×3) эквивалентна проверке делимости на 8 (2 ³ ) и 3 одновременно, таким образом, нам нужно показать делимость только на 8 и на 3, чтобы доказать делимость на 24. ${\displaystyle p_{1}^{n}p_{2}^{m}p_{3}^{q}}$

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30

Пошаговые примеры

Делимость на 2

Сначала возьмите любое число (в этом примере это будет 376) и запишите последнюю цифру в числе, отбросив остальные цифры. Затем возьмите эту цифру (6), игнорируя остальную часть числа, и определите, делится ли она на 2. Если она делится на 2, то исходное число делится на 2.

Пример

1. 376 (исходный номер)
2. 37 6 (Возьмите последнюю цифру)
3. 6 ÷ 2 = 3 (Проверьте, делится ли последняя цифра на 2)
4. 376 ÷ 2 = 188 (Если последняя цифра делится на 2, то и все число делится на 2)

Делимость на 3 или 9

Сначала возьмем любое число (в данном примере это будет 492) и сложим все цифры в числе (4 + 9 + 2 = 15). Затем возьмем эту сумму (15) и определим, делится ли она на 3. Исходное число делится на 3 (или 9) тогда и только тогда, когда сумма его цифр делится на 3 (или 9).

Сложение цифр числа и последующее повторение процесса с результатом до тех пор, пока не останется только одна цифра, даст остаток исходного числа, если его разделить на девять (если только эта единственная цифра сама не девять, в этом случае число делится на девять, а остаток равен нулю).

Это можно обобщить на любую стандартную позиционную систему счисления , в которой рассматриваемый делитель становится на единицу меньше основания ; таким образом, в двенадцатой системе счисления при делении на одиннадцать цифры в сумме дадут остаток исходного числа, а числа делятся на одиннадцать только в том случае, если сумма цифр делится на одиннадцать.

Пример.

1. 492 (исходный номер)
2. 4 + 9 + 2 = 15 (сложите каждую отдельную цифру)
3. 15 делится на 3, и на этом мы можем остановиться. Или же мы можем продолжить использовать тот же метод, если число все еще слишком велико:
4. 1 + 5 = 6 (сложите каждую отдельную цифру)
5. 6 ÷ 3 = 2 (Проверьте, делится ли полученное число на 3)
6. 492 ÷ 3 = 164 (Если число, полученное с помощью правила, делится на 3, то и все число делится на 3)

Делимость на 4

Основное правило делимости на 4 заключается в том, что если число, образованное двумя последними цифрами числа, делится на 4, то и исходное число делится на 4; ^{[2] [3]} это происходит потому, что 100 делится на 4, и поэтому прибавление сотен, тысяч и т. д. — это просто прибавление еще одного числа, которое делится на 4. Если какое-либо число заканчивается двузначным числом, которое, как вы знаете, делится на 4 (например, 24, 04, 08 и т. д.), то все число будет делиться на 4 независимо от того, что стоит перед последними двумя цифрами.

В качестве альтернативы можно просто прибавить половину последней цифры к предпоследней цифре (или оставшемуся числу). Если это число является четным натуральным числом, то исходное число делится на 4

Также можно просто разделить число на 2, а затем проверить результат, чтобы узнать, делится ли оно на 2. Если это так, то исходное число делится на 4. Кроме того, результат этого теста такой же, как и исходное число, деленное на 4.

Пример.
Общее правило

1. 2092 (исходный номер)
2. 20 92 (Возьмите последние две цифры числа, отбросив все остальные цифры)
3. 92 ÷ 4 = 23 (Проверьте, делится ли число на 4)
4. 2092 ÷ 4 = 523 (Если полученное число делится на 4, то исходное число делится на 4)

Второй метод

1. 6174 (исходный номер)
2. проверьте, что последняя цифра четная, иначе 6174 не может делиться на 4.
3. 61 7 4 (Отделите последние 2 цифры от остальной части числа)
4. 4 ÷ 2 = 2 (последняя цифра делится на 2)
5. 7 + 2 = 9 (Добавьте половину последней цифры к предпоследней цифре)
6. Так как 9 не является четным числом, 6174 не делится на 4.

Третий способ

1. 1720 (первоначальный номер)
2. 1720 ÷ 2 = 860 (Разделите исходное число на 2)
3. 860 ÷ 2 = 430 (Проверьте, делится ли результат на 2)
4. 1720 ÷ 4 = 430 (Если результат делится на 2, то исходное число делится на 4)

Делимость на 5

Делимость на 5 легко определяется проверкой последней цифры в числе (47 5 ) и определением, является ли она 0 или 5. Если последняя цифра равна 0 или 5, то все число делится на 5. ^{[2] [3]}

Если последняя цифра в числе — 0, то результатом будут оставшиеся цифры, умноженные на 2. Например, число 40 заканчивается на ноль, поэтому берем оставшиеся цифры (4) и умножаем их на два (4 × 2 = 8). Результат такой же, как и результат деления 40 на 5 (40/5 = 8).

Если последняя цифра в числе — 5, то результатом будут оставшиеся цифры, умноженные на два, плюс один. Например, число 125 заканчивается на 5, поэтому берем оставшиеся цифры (12), умножаем их на два (12 × 2 = 24), затем прибавляем один (24 + 1 = 25). Результат такой же, как и результат деления 125 на 5 (125/5=25).

Пример.
Если последняя цифра 0

1. 110 (исходный номер)
2. 11 0 (Возьмите последнюю цифру числа и проверьте, является ли она 0 или 5)
3. 11 0 (Если это 0, то берем оставшиеся цифры, отбрасывая последнюю)
4. 11 × 2 = 22 (Умножьте результат на 2)
5. 110 ÷ 5 = 22 (Результат такой же, как исходное число, деленное на 5)

Если последняя цифра 5

1. 85 (исходное число)
2. 8 5 (Возьмите последнюю цифру числа и проверьте, является ли она 0 или 5)
3. 8 5 (Если это 5, возьмите оставшиеся цифры, отбросив последнюю)
4. 8 × 2 = 16 (Умножьте результат на 2)
5. 16 + 1 = 17 (Добавьте 1 к результату)
6. 85 ÷ 5 = 17 (Результат такой же, как исходное число, деленное на 5)

Делимость на 6

Делимость на 6 определяется путем проверки исходного числа, чтобы увидеть, является ли оно одновременно четным числом (делится на 2) и делится на 3. ^[6]

Если конечная цифра четная, то число делится на два и, следовательно, может делиться на 6. Если число делится на 2, продолжайте складывать цифры исходного числа и проверять, кратна ли эта сумма 3. Любое число, которое одновременно кратно 2 и 3, кратно 6.

Пример.

1. 324 (исходный номер)
2. Последняя цифра 4 — четная, поэтому 324 делится на 2 и может делиться на 6.
3. 3 + 2 + 4 = 9, что кратно 3. Следовательно, исходное число делится как на 2, так и на 3, а также делится на 6.

Делимость на 7

Делимость на 7 можно проверить рекурсивным методом. Число вида 10 x  +  y делится на 7 тогда и только тогда, когда x  − 2 y делится на 7. Другими словами, вычтите дважды последнюю цифру из числа, образованного оставшимися цифрами. Продолжайте делать это до тех пор, пока не получится число, для которого известно, делится ли оно на 7. Исходное число делится на 7 тогда и только тогда, когда число, полученное с помощью этой процедуры, делится на 7. Например, число 371: 37 − (2 × 1) = 37 − 2 = 35; 3 − (2 × 5) = 3 − 10 = −7; таким образом, поскольку −7 делится на 7, 371 делится на 7.

Аналогично число вида 10 x  +  y делится на 7 тогда и только тогда, когда x  + 5 y делится на 7. ^[8] Итак, прибавьте пять раз последнюю цифру к числу, образованному оставшимися цифрами, и продолжайте делать это до тех пор, пока не получится число, для которого будет известно, делится ли оно на 7. ^[9]

Другой метод — умножение на 3. Число вида 10 x  +  y имеет тот же остаток при делении на 7, что и 3 x  +  y . Нужно умножить самую левую цифру исходного числа на 3, добавить следующую цифру, взять остаток при делении на 7 и продолжить с начала: умножить на 3, добавить следующую цифру и т. д. Например, число 371: 3×3 + 7 = 16 остаток 2 и 2×3 + 1 = 7. Этот метод можно использовать для нахождения остатка от деления на 7.

Более сложный алгоритм проверки делимости на 7 использует тот факт, что 10 ⁰  ≡ 1, 10 ¹  ≡ 3, 10 ²  ≡ 2, 10 ³  ≡ 6, 10 ⁴  ≡ 4, 10 ⁵  ≡ 5, 10 ⁶  ≡ 1, ... (mod 7). Возьмите каждую цифру числа (371) в обратном порядке (173), умножая их последовательно на цифры 1 , 3 , 2 , 6 , 4 , 5 , повторяя эту последовательность множителей столько, сколько необходимо (1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, ...), и складывая произведения (1× 1  + 7× 3  + 3× 2 = 1 + 21 + 6 = 28). Исходное число делится на 7 тогда и только тогда, когда число, полученное с помощью этой процедуры, делится на 7 (следовательно, 371 делится на 7, поскольку 28 делится на 7). ^[10]

Этот метод можно упростить, устранив необходимость умножения. Все, что потребуется при таком упрощении, — это запомнить последовательность выше (132645...), а также складывать и вычитать, но всегда работая с однозначными числами.

Упрощение выглядит следующим образом:

• Возьмем к примеру число 371
• Измените все вхождения 7 , 8 или 9 на 0 , 1 и 2 соответственно. В этом примере мы получаем: 301. Этот второй шаг можно пропустить, за исключением самой левой цифры, но его выполнение может облегчить вычисления в дальнейшем.
• Теперь преобразуем первую цифру (3) в следующую цифру в последовательности 13264513... В нашем примере 3 становится 2 .
• Добавьте результат предыдущего шага (2) ко второй цифре числа и подставьте результат вместо обеих цифр, оставив все оставшиеся цифры без изменений: 2 + 0 = 2. Таким образом, 30 1 становится 2 1 .
• Повторяйте процедуру до тех пор, пока не получите распознаваемое число, кратное 7, или, чтобы быть уверенным, число от 0 до 6. Итак, начиная с 21 (которое является распознаваемым числом, кратным 7), возьмите первую цифру (2) и преобразуйте ее в следующую последовательность в приведенной выше последовательности: 2 становится 6. Затем добавьте это ко второй цифре: 6 + 1 =  7 .
• Если в какой-то момент первой цифрой будет 8 или 9, они станут 1 или 2 соответственно. Но если это 7, то она должна стать 0, только если за ней не последует никаких других цифр. В противном случае ее следует просто отбросить. Это потому, что 7 стала бы 0, а числа с по крайней мере двумя цифрами перед десятичной точкой не начинаются с 0, что бесполезно. Согласно этому, наша 7 становится  0 .

Если в результате этой процедуры вы получите 0 или любое распознаваемое число, кратное 7, то исходное число будет кратным 7. Если вы получите любое число от 1 до 6 , это будет указывать, сколько вам следует вычесть из исходного числа, чтобы получить число, кратное 7. Другими словами, вы найдете остаток от деления числа на 7. Например, возьмем число  186 :

• Сначала измените 8 на 1: 116 .
• Теперь замените 1 на следующую цифру в последовательности (3), добавьте ее ко второй цифре и запишите результат вместо обеих: 3 + 1 =  4. Таким образом, 11 6 теперь становится 4 6 .
• Повторите процедуру, поскольку число больше 7. Теперь 4 становится 5, что нужно прибавить к 6. Это  11 .
• Повторите процедуру еще раз: 1 становится 3, которая прибавляется ко второй цифре (1): 3 + 1 =  4 .

Теперь у нас есть число меньше 7, и это число (4) является остатком от деления 186/7. Таким образом, 186 минус 4, что равно 182, должно быть кратно 7.

Примечание: Причина, по которой это работает, заключается в том, что если у нас есть: a+b=c и b является кратным любому заданному числу n , то a и c обязательно дадут одинаковый остаток при делении на n . Другими словами, в 2 + 7 = 9, 7 делится на 7. Поэтому 2 и 9 должны иметь одинаковый остаток при делении на 7. Остаток равен 2.

Следовательно, если число n кратно 7 (т. е. остаток от n /7 равен 0), то прибавление (или вычитание) чисел, кратных 7, не может изменить это свойство.

Что делает эта процедура, как объяснялось выше для большинства правил делимости, это просто вычитание понемногу кратных 7 из исходного числа до тех пор, пока не достигнет числа, которое достаточно мало для того, чтобы мы могли запомнить, кратно ли оно 7. Если 1 становится 3 в следующей десятичной позиции, это то же самое, что и преобразование 10×10 ⁿ в 3×10 ⁿ . И это на самом деле то же самое, что вычитание 7×10 ⁿ (очевидно, кратно 7) из 10×10 ⁿ .

Аналогично, когда вы превращаете 3 в 2 в следующей десятичной позиции, вы превращаете 30×10 ⁿ в 2×10 ⁿ , что то же самое, что вычитание 30×10 ⁿ −28×10 ⁿ , и это снова вычитание числа, кратного 7. Та же причина применима ко всем оставшимся преобразованиям:

• 20×10 ⁿ  − 6×10 ⁿ = 14 ×10 ⁿ
• 60×10 ⁿ  − 4×10 ⁿ = 56 ×10 ⁿ
• 40×10 ⁿ  − 5×10 ⁿ = 35 ×10 ⁿ
• 50×10 ⁿ  − 1×10 ⁿ = 49 ×10 ⁿ

Пример первого метода
1050 → 105 − 0=105 → 10 − 10 = 0. ОТВЕТ: 1050 делится на 7.

Пример второго метода
1050 → 0501 (обратный) → 0× 1 + 5× 3 + 0× 2 + 1× 6 = 0 + 15 + 0 + 6 = 21 (умножить и сложить). ОТВЕТ: 1050 делится на 7.

Ведический метод делимости соприкосновением
Делимость на семь можно проверить умножением по Экхадике . Преобразуйте делитель семь в семейство девяток, умножив на семь. 7×7=49. Добавьте единицу, отбросьте цифру единиц и возьмите 5, Экхадику , в качестве множителя. Начните справа. Умножьте на 5, добавьте произведение к следующей цифре слева. Запишите этот результат на строке под этой цифрой. Повторите этот метод умножения цифры единиц на пять и прибавления этого произведения к числу десятков. Добавьте результат к следующей цифре слева. Запишите этот результат под цифрой. Продолжайте до конца. Если результат равен нулю или кратен семи, то да, число делится на семь. В противном случае — нет. Это соответствует ведическому идеалу, однострочной записи. ^{[11] [ ненадежный источник? ]}

Пример ведического метода:

Делится ли 438 722 025 на семь? Множитель = 5. 4 3 8 7 2 2 0 2 542 37 46 37 6 40 37 27ДА

Метод Полмана–Масса делимости на 7
Метод Полмана–Масса обеспечивает быстрое решение, которое может определить, делятся ли большинство целых чисел на семь за три шага или меньше. Этот метод может быть полезен в математическом конкурсе, таком как MATHCOUNTS, где время является фактором для определения решения без калькулятора в раунде спринта.

Шаг A: Если целое число равно 1000 или меньше, вычтите дважды последнюю цифру из числа, образованного оставшимися цифрами. Если результат кратен семи, то исходное число также кратно семи (и наоборот). Например:

112 -> 11 − (2×2) = 11 − 4 = 7 ДА98 -> 9 − (8×2) = 9 − 16 = −7 ДА634 -> 63 − (4×2) = 63 − 8 = 55 НЕТ

Поскольку 1001 делится на семь, интересная закономерность развивается для повторяющихся наборов из 1, 2 или 3 цифр, которые образуют 6-значные числа (ведущие нули допускаются), поскольку все такие числа делятся на семь. Например:

001 001 = 1001 / 7 = 143010 010 = 10 010 / 7 = 1 430011 011 = 11 011 / 7 = 1 573100 100 = 100 100 / 7 = 14 300101 101 = 101 101 / 7 = 14 443110 110 = 110 110 / 7 = 15 730

01 01 01 = 10,101 / 7 = 1,44310 10 10 = 101 010 / 7 = 14 430

111,111 / 7 = 15,873222,222 / 7 = 31,746999 999 / 7 = 142 857

576 576 / 7 = 82 368

Для всех приведенных выше примеров вычитание первых трех цифр из последних трех дает результат, кратный семи. Обратите внимание, что начальные нули разрешены для формирования 6-значного шаблона.

Это явление лежит в основе шагов B и C.

Шаг B: Если целое число находится в диапазоне от 1001 до одного миллиона, найдите повторяющуюся последовательность из 1, 2 или 3 цифр, которая образует 6-значное число, близкое к целому числу (ведущие нули допускаются и могут помочь вам визуализировать последовательность). Если положительная разность меньше 1000, примените шаг A. Это можно сделать, вычитая первые три цифры из последних трех цифр. Например:

341,355 − 341,341 = 14 -> 1 − (4×2) = 1 − 8 = −7 ДА 67,326 − 067,067 = 259 -> 25 − (9×2) = 25 − 18 = 7 ДА

Тот факт, что 999 999 кратно 7, можно использовать для определения делимости целых чисел, больших миллиона, путем сокращения целого числа до 6-значного числа, которое можно определить с помощью шага B. Это можно легко сделать, прибавив цифры слева от первых шести к последним шести и выполнив шаг A.

Шаг C: Если целое число больше миллиона, вычтите ближайшее кратное 999 999, а затем примените шаг B. Для еще больших чисел используйте большие наборы, такие как 12-значные (999 999 999 999) и т. д. Затем разбейте целое число на меньшее число, которое можно решить с помощью шага B. Например:

22 862 420 — (999 999 × 22) = 22 862 420 — 21 999 978 -> 862 420 + 22 = 862 442 862,442 -> 862 − 442 (Шаг B) = 420 -> 42 − (0×2) (Шаг A) = 42 ДА

Это позволяет складывать и вычитать чередующиеся наборы из трех цифр для определения делимости на семь. Понимание этих закономерностей позволяет вам быстро вычислять делимость на семь, как показано в следующих примерах:

Метод Полмана–Масса делимости на 7, примеры:

Делится ли 98 на семь?98 -> 9 − (8×2) = 9 − 16 = −7 ДА (Шаг A)

Делится ли 634 на семь?634 -> 63 − (4×2) = 63 − 8 = 55 НЕТ (Шаг A)

Делится ли 355 341 на семь?355 341 − 341 341 = 14 000 (Шаг B) -> 014 − 000 (Шаг B) -> 14 = 1 − (4×2) (Шаг A) = 1 − 8 = −7 ДА

Делится ли 42 341 530 на семь?42,341,530 -> 341,530 + 42 = 341,572 (Шаг C)341,572 − 341,341 = 231 (Шаг B)231 -> 23 − (1×2) = 23 − 2 = 21 ДА (Шаг A)

Используя быстрые чередующиеся сложения и вычитания: 42,341,530 -> 530 − 341 + 42 = 189 + 42 = 231 -> 23 − (1×2) = 21 ДА

Умножение на 3, способ делимости на 7, примеры:

Делится ли 98 на семь?98 -> 9 остаток 2 -> 2×3 + 8 = 14 ДА

Делится ли 634 на семь?634 -> 6×3 + 3 = 21 -> остаток 0 -> 0×3 + 4 = 4 НЕТ

Делится ли 355 341 на семь?3 × 3 + 5 = 14 -> остаток 0 -> 0×3 + 5 = 5 -> 5×3 + 3 = 18 -> остаток 4 -> 4×3 + 4 = 16 -> остаток 2 -> 2×3 + 1 = 7 ДА

Найдите остаток от деления 1036125837 на 71×3 + 0 = 33×3 + 3 = 12 остаток 55×3 + 6 = 21 остаток 00×3 + 1 = 11×3 + 2 = 55×3 + 5 = 20 остаток 66×3 + 8 = 26 остаток 55×3 + 3 = 18 остаток 44×3 + 7 = 19 остаток 5Ответ 5.

Нахождение остатка числа при делении на 7

7 − (1, 3, 2, −1, −3, −2, цикл повторяется для следующих шести цифр) Период: 6 цифр. Повторяющиеся числа: 1, 3, 2, −1, −3, −2
Минимальная последовательность величин
(1, 3, 2, 6, 4, 5, цикл повторяется для следующих шести цифр) Период: 6 цифр. Повторяющиеся числа: 1, 3, 2, 6, 4, 5
Положительная последовательность

Умножьте самую правую цифру на самую левую цифру в последовательности и умножьте вторую справа цифру на вторую слева цифру в последовательности и так далее и так далее. Затем вычислите сумму всех значений и возьмите модуль 7.
Пример: каков остаток при делении 1036125837 на 7?

Умножение самой правой цифры = 1 × 7 = 7

Умножение второй самой правой цифры = 3 × 3 = 9

Третья самая правая цифра = 8 × 2 = 16

Четвертая самая правая цифра = 5 × −1 = −5

Пятая самая правая цифра = 2 × −3 = −6

Шестая самая правая цифра = 1 × −2 = −2

Седьмая самая правая цифра = 6 × 1 = 6

Восьмая самая правая цифра = 3 × 3 = 9

Девятая самая правая цифра = 0

Десятая самая правая цифра = 1 × −1 = −1

Сумма = 33

33 модуль 7 = 5

Остаток = 5

Метод пар цифр делимости на 7

Этот метод использует шаблон 1 , −3 , 2 для пар цифр . То есть делимость любого числа на семь можно проверить, сначала разделив число на пары цифр, а затем применив алгоритм к трем парам цифр (шести цифрам). Если число меньше шести цифр, то заполните нули справа, пока не получится шесть цифр. Если число больше шести цифр, то повторите цикл для следующей группы из шести цифр, а затем сложите результаты. Повторяйте алгоритм, пока результатом не станет небольшое число. Исходное число делится на семь тогда и только тогда, когда число, полученное с помощью этого алгоритма, делится на семь. Этот метод особенно подходит для больших чисел.

Пример 1:
Число для проверки — 157514. Сначала мы разделим число на три пары цифр: 15, 75 и 14.
Затем мы применим алгоритм: 1 × 15 − 3 × 75 + 2 × 14 = 182
Поскольку полученное 182 меньше шести цифр, мы добавляем нули в правую часть, пока не станет шесть цифр.
Затем мы снова применяем наш алгоритм: 1 × 18 − 3 × 20 + 2 × 0 = −42
Результат −42 делится на семь, поэтому исходное число 157514 делится на семь.

Пример 2:
Число для проверки — 15751537186.
( 1 × 15 − 3 × 75 + 2 × 15) + ( 1 × 37 − 3 × 18 + 2 × 60) = −180 + 103 = −77
Результат −77 делится на семь, поэтому исходное число 15751537186 ​​делится на семь.

Другой метод пар цифр делимости на 7

Метод

Это нерекурсивный метод нахождения остатка от деления числа на 7:

1. Разделите число на пары цифр, начиная с единицы. При необходимости добавьте к числу 0, чтобы завершить последнюю пару.
2. Вычислите остатки, которые дает каждая пара цифр при делении на 7.
3. Умножьте остатки на соответствующий множитель из последовательности 1, 2, 4, 1, 2, 4, ...: остаток от пары цифр, состоящей из разряда единиц и разряда десятков, следует умножить на 1, сотни и тысячи — на 2, десятки тысяч и сотни тысяч — на 4, миллион и десять миллионов снова на 1 и так далее.
4. Рассчитайте остатки, которые дает каждое произведение при делении на 7.
5. Сложите эти остатки.
6. Остаток суммы при делении на 7 равен остатку данного числа при делении на 7.

Например:

Число 194 536 при делении на 7 дает остаток 6.

Число 510 517 813 при делении на 7 дает остаток 1.

Доказательство правильности метода

Метод основан на наблюдении, что 100 дает остаток 2 при делении на 7. И поскольку мы разбиваем число на пары цифр, мы по сути имеем степени числа 100.

1 мод 7 = 1

100 мод 7 = 2

10 000 mod 7 = 2^2 = 4

1 000 000 по модулю 7 = 2 ^ 3 = 8; 8 мод 7 = 1

100 000 000 по модулю 7 = 2^4 = 16; 16 мод 7 = 2

10 000 000 000 по модулю 7 = 2^5 = 32; 32 мод 7 = 4

И так далее.

Корректность метода устанавливается тогда следующей цепочкой равенств:

Пусть N — заданное число . ${\displaystyle {\overline {a_{2n}a_{2n-1}...a_{2}a_{1}}}}$

${\displaystyle {\overline {a_{2n}a_{2n-1}...a_{2}a_{1}}}\mod 7}$

${\displaystyle [\sum _{k=1}^{n}(a_{2k}a_{2k-1})\times 10^{2k-2}]{\bmod {7}}}$

${\displaystyle \sum _{k=1}^{n}(a_{2k}a_{2k-1}\times 10^{2k-2}){\bmod {7}}}$

${\displaystyle \sum _{k=1}^{n}(a_{2k}a_{2k-1}{\bmod {7}})\times (10^{2k-2}{\bmod {7}})}$

Делимость на 11

Метод

Чтобы проверить делимость на 11, рассмотрим чередующуюся сумму цифр. Например, для 907 071:

${\displaystyle 9-0+7-0+7-1=22=2\times 11,}$

поэтому 907 071 делится на 11.

Мы можем начать с или , поскольку умножение целого на ничего не меняет. ${\displaystyle -}$ ${\displaystyle +}$ ${\displaystyle -1}$

Доказательство правильности метода

Учитывая, что , мы можем записать для любого целого числа: ${\displaystyle 10\equiv -1{\bmod {1}}1}$

${\displaystyle {\overline {a_{n}a_{n-1}...a_{1}a_{0}}}=\sum _{i=0}^{n}a_{i}10^{i}\equiv \sum _{i=0}^{n}(-1)^{i}a_{i}{\bmod {1}}1.}$

Делимость на 13

Тест на остаток 13 (1, −3, −4, −1, 3, 4, цикл продолжается.) Если вам некомфортно с отрицательными числами, то используйте эту последовательность. (1, 10, 9, 12, 3, 4)

Умножьте самую правую цифру числа на самую левую цифру в последовательности, показанной выше, а вторую самую правую цифру на вторую самую левую цифру числа в последовательности. Цикл продолжается.

Пример: Каков остаток при делении 321 на 13?
Используя первую последовательность,
Ответ: 1 × 1 + 2 × −3 + 3 × −4 = −17
Остаток = −17 mod 13 = 9

Пример: Каков остаток при делении 1234567 на 13?
Используя вторую последовательность,
ответ: 7 × 1 + 6 × 10 + 5 × 9 + 4 × 12 + 3 × 3 + 2 × 4 + 1 × 1 = 178 mod 13 = 9
Остаток = 9

Рекурсивный метод может быть получен с использованием того факта, что и что . Это подразумевает, что число делится на 13 тогда и только тогда, когда удаление первой цифры и вычитание 3 раз этой цифры из новой первой цифры дает число, делящееся на 13. У нас также есть правило, что 10 x + y делится тогда и только тогда, когда x + 4 y делится на 13. Например, чтобы проверить делимость 1761 на 13, мы можем свести это к делимости 461 по первому правилу. Используя второе правило, это сводится к делимости 50, и, сделав это снова, получаем 5. Таким образом, 1761 не делится на 13. ${\displaystyle 10=-3{\bmod {1}}3}$ ${\displaystyle 10^{-1}=4{\bmod {1}}3}$

Проверка числа 871 таким образом сводит его к делимости на 91 с использованием второго правила, а затем к делимости на 13 с использованием этого правила еще раз, поэтому мы видим, что 871 делится на 13.

После 30

Свойства делимости чисел можно определить двумя способами в зависимости от типа делителя.

Составные делители

Число делится на заданный делитель, если оно делится на наивысшую степень каждого из своих простых множителей. Например, чтобы определить делимость на 36, проверьте делимость на 4 и на 9. ^[6] Обратите внимание, что проверки 3 и 12 или 2 и 18 будет недостаточно. Таблица простых множителей может оказаться полезной.

Составной делитель также может иметь правило, сформированное с использованием той же процедуры, что и для простого делителя, приведенной ниже, с оговоркой, что задействованные манипуляции не могут ввести какой-либо множитель, который присутствует в делителе. Например, нельзя создать правило для 14, которое включает умножение уравнения на 7. Это не проблема для простых делителей, потому что у них нет меньших множителей.

Простые делители

Цель состоит в том, чтобы найти обратное к 10 по модулю рассматриваемого простого числа (не работает для 2 или 5) и использовать его в качестве множителя, чтобы сделать делимость исходного числа на это простое число зависящей от делимости нового (обычно меньшего) числа на то же самое простое число. Используя 31 в качестве примера, поскольку 10 × (−3) = −30 = 1 mod 31, мы получаем правило для использования y  − 3 x в таблице ниже. Аналогично, поскольку 10 × (28) = 280 = 1 mod 31, мы получаем дополнительное правило y  + 28 x того же рода — наш выбор сложения или вычитания продиктован арифметическим удобством меньшего значения. Фактически, это правило для простых делителей, кроме 2 и 5, на самом деле является правилом делимости на любое целое число, взаимно простое с 10 (включая 33 и 39; см. таблицу ниже). Вот почему последнее условие делимости в таблицах выше и ниже для любого числа, взаимно простого с 10, имеет одинаковую форму (прибавить или вычесть некоторое кратное последней цифры из оставшейся части числа).

Обобщенное правило делимости

Для проверки делимости на D , где D заканчивается на 1, 3, 7 или 9, можно использовать следующий метод. ^[12] Найдите любое кратное D, оканчивающееся на 9. (Если D заканчивается соответственно на 1, 3, 7 или 9, то умножьте на 9, 3, 7 или 1.) Затем прибавьте 1 и разделите на 10, обозначив результат как m . Тогда число N = 10 t + q делится на D тогда и только тогда, когда mq + t делится на D . Если число слишком велико, вы также можете разбить его на несколько строк с e цифрами в каждой, удовлетворяющих либо 10 ^e = 1, либо 10 ^e = −1 (mod D ). Сумма (или чередующаяся сумма) чисел имеет ту же делимость, что и исходная.

Например, чтобы определить, делится ли 913 = 10×91 + 3 на 11, найдите, что m = (11×9+1)÷10 = 10. Тогда mq+t = 10×3+91 = 121; это делится на 11 (с частным 11), поэтому 913 также делится на 11. В качестве другого примера, чтобы определить, делится ли 689 = 10×68 + 9 на 53, найдите, что m = (53×3+1)÷10 = 16. Тогда mq+t = 16×9 + 68 = 212, что делится на 53 (с частным 4); поэтому 689 также делится на 53.

Альтернативно, любое число Q = 10c + d делится на n = 10a + b, так что gcd(n, 2, 5) = 1, если c + D(n)d = An для некоторого целого числа A, где: ${\displaystyle D(n)\equiv {\begin{cases}9a+1,&{\mbox{if }}n{\mbox{ = 10a+1}}\\3a+1,&{\mbox{if }}n{\mbox{ = 10a+3}}\\7a+5,&{\mbox{if }}n{\mbox{ = 10a+7}}\\a+1,&{\mbox{if }}n{\mbox{ = 10a+9}}\end{cases}}\ }$

Первые несколько членов последовательности, сгенерированной D(n), — это 1, 1, 5, 1, 10, 4, 12, 2, ... (последовательность A333448 в OEIS ).

Кусочная форма D(n) и последовательность, ею генерируемая, были впервые опубликованы болгарским математиком Иваном Стойковым в марте 2020 года. ^[13]

Доказательства

Доказательство с использованием элементарной алгебры

Многие из более простых правил можно получить, используя только алгебраические манипуляции, создавая биномы и переставляя их. Записывая число как сумму каждой цифры, умноженную на степень 10, можно манипулировать степенью каждой цифры по отдельности.

Случай, когда все цифры суммируются

Этот метод работает для делителей, являющихся множителями 10 − 1 = 9.

Используя 3 в качестве примера, 3 делит 9 = 10 − 1. Это означает (см. модульную арифметику ). То же самое для всех высших степеней 10: они все сравнимы с 1 по модулю 3. Поскольку два числа, сравнимые по модулю 3, либо оба делятся на 3, либо оба нет, мы можем поменять местами значения, сравнимые по модулю 3. Таким образом, в таком числе, как следующее, мы можем заменить все степени 10 на 1: ${\displaystyle 10\equiv 1{\pmod {3}}}$ ${\displaystyle 10^{n}\equiv 1^{n}\equiv 1{\pmod {3}}}$

${\displaystyle 100\cdot a+10\cdot b+1\cdot c\equiv (1)a+(1)b+(1)c{\pmod {3}}}$

что в точности равно сумме цифр.

Случай, когда используется чередующаяся сумма цифр

Этот метод работает для делителей, являющихся множителями 10 + 1 = 11.

Используя 11 в качестве примера, 11 делит 11 = 10 + 1. Это означает . Для более высоких степеней 10 они сравнимы с 1 для четных степеней и сравнимы с −1 для нечетных степеней: ${\displaystyle 10\equiv -1{\pmod {11}}}$

${\displaystyle 10^{n}\equiv (-1)^{n}\equiv {\begin{cases}1,&{\mbox{if }}n{\mbox{ is even}}\\-1,&{\mbox{if }}n{\mbox{ is odd}}\end{cases}}{\pmod {11}}.}$

Как и в предыдущем случае, мы можем заменить степени числа 10 на конгруэнтные значения:

${\displaystyle 1000\cdot a+100\cdot b+10\cdot c+1\cdot d\equiv (-1)a+(1)b+(-1)c+(1)d{\pmod {11}}}$

что также представляет собой разницу между суммой цифр на нечетных позициях и суммой цифр на четных позициях.

Случай, когда важны только последние цифры

Это применимо к делителям, которые являются множителями степени числа 10. Это связано с тем, что достаточно высокие степени основания кратны делителю и могут быть исключены.

Например, в десятичной системе счисления множители числа 10 ¹ включают 2, 5 и 10. Поэтому делимость на 2, 5 и 10 зависит только от того, делится ли последняя цифра 1 на эти делители. Множители числа 10 ² включают 4 и 25, а делимость на них зависит только от последних 2 цифр.

Случай, когда удаляются только последние цифры

Большинство чисел не делят нацело 9 или 10, но делят более высокую степень 10 ⁿ или 10 ⁿ  − 1. В этом случае число по-прежнему записывается в виде степеней 10, но не полностью развернуто.

Например, 7 не делит 9 или 10, но делит 98, что близко к 100. Таким образом, исходим из

${\displaystyle 100\cdot a+b}$

где в этом случае a — любое целое число, а b может находиться в диапазоне от 0 до 99. Далее,

${\displaystyle (98+2)\cdot a+b}$

и снова расширяется

${\displaystyle 98\cdot a+2\cdot a+b,}$

и после исключения известного кратного 7, результат будет

${\displaystyle 2\cdot a+b,}$

которое заключается в правиле «удвоить число, образованное всеми цифрами, кроме последних двух, затем сложить последние две цифры».

Случай, когда последняя цифра(ы) умножается на коэффициент

Представление числа также может быть умножено на любое число, относительно простое к делителю, не изменяя его делимости. Заметив, что 7 делит 21, мы можем выполнить следующее:

${\displaystyle 10\cdot a+b,}$

после умножения на 2 это становится

${\displaystyle 20\cdot a+2\cdot b,}$

а потом

${\displaystyle (21-1)\cdot a+2\cdot b.}$

Устранение 21 дает

${\displaystyle -1\cdot a+2\cdot b,}$

и умножение на −1 дает

${\displaystyle a-2\cdot b.}$

Можно использовать любое из последних двух правил, в зависимости от того, какое из них проще выполнить. Они соответствуют правилу «вычесть дважды последнюю цифру из остатка».

Доказательство с использованием модульной арифметики

В этом разделе будет проиллюстрирован базовый метод; все правила могут быть выведены с помощью той же процедуры. Для следующего требуется базовая основа в модульной арифметике ; для делимости, отличной от 2 и 5, доказательства опираются на базовый факт, что 10 mod m обратимо, если 10 и m взаимно просты.

Для 2 ^н или 5 ^н :

Необходимо проверить только последние n цифр.

${\displaystyle 10^{n}=2^{n}\cdot 5^{n}\equiv 0{\pmod {2^{n}\mathrm {\ or\ } 5^{n}}}}$

Представляя x как ${\displaystyle 10^{n}\cdot y+z,}$

${\displaystyle x=10^{n}\cdot y+z\equiv z{\pmod {2^{n}\mathrm {\ or\ } 5^{n}}}}$

и делимость x такая же, как и у z .

Для 7:

Поскольку 10 × 5 ≡ 10 × (−2) ≡ 1 (mod 7), мы можем сделать следующее:

Представляя x как ${\displaystyle 10\cdot y+z,}$

${\displaystyle -2x\equiv y-2z{\pmod {7}},}$

поэтому x делится на 7 тогда и только тогда, когда y − 2 z делится на 7.

Смотрите также

• Деление на ноль
• Четность (математика)

Ссылки

1. Гарднер, Мартин (сентябрь 1962 г.). «Математические игры: тесты, показывающие, можно ли разделить большое число на число от 2 до 12». Scientific American . 207 (3): 232–246. doi :10.1038/scientificamerican0962-232. JSTOR  24936675.
2. Это следует из критерия Паскаля. См. Kisačanin (1998), стр. 100–101
3. Число делится на 2 ^m , 5 ^m или 10 ^m тогда и только тогда, когда число, образованное последними m цифрами, делится на это число. См. Richmond & Richmond (2009), стр. 105
4. Apostol (1976), стр. 108
5. Richmond & Richmond (2009), Раздел 3.4 (Тесты делимости), стр. 102–108
6. Richmond & Richmond (2009), раздел 3.4 (Признаки делимости), теорема 3.4.3, с. 107
7. Кисачанин (1998), с. 101
8. Loy, Jim (1999), Divisibility Tests, архивировано из оригинала 2007-10-10, Умножьте самую правую цифру на 5 и добавьте к остальным числам. Если эта сумма делится на 7, то исходное число делится на 7.
9. Уэллс, Дэвид (1997), Словарь любопытных и интересных чисел издательства Penguin, стр. 51, ISBN 9780140261493
10. Su, Francis E. ""Divisibility by Seven" Mudd Math Fun Facts". Архивировано из оригинала 2019-06-13 . Получено 2006-12-12 .
11. Страница 274, Ведическая математика: шестнадцать простых математических формул , Свами Шанкарачарья, опубликовано Motilal Banarsidass, Варанаси, Индия, 1965, Дели, 1978. 367 страниц.
12. Данкельс, Андрейс, «Комментарии к примечанию 82.53 — обобщенный тест на делимость», Mathematical Gazette 84, март 2000 г., 79-81.
13. Стойков, Иван (март 2020 г.). «ОЭИС А333448». Оеис А333448 .

Источники

• Апостол, Том М. (1976). Введение в аналитическую теорию чисел . Бакалаврские тексты по математике . Том 1. Springer-Verlag. ISBN 978-0-387-90163-3.
• Кисачанин, Бранислав (1998). Математические проблемы и доказательства: комбинаторика, теория чисел и геометрия . Plenum Press. ISBN 978-0-306-45967-2.
• Ричмонд, Беттина ; Ричмонд, Томас (2009). Дискретный переход к высшей математике . Чистые и прикладные тексты для бакалавриата. Том 3. Американское математическое общество. ISBN 978-0-8218-4789-3.

Внешние ссылки

• Критерии делимости при разрубании узла
• Глупые трюки с делимостью. Правила делимости от 2 до 100.