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

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

Правила делимости чисел 1–30 [ править ]

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

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

Примечание. Чтобы проверить делимость на любое число, которое может быть выражено как 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}}$

Пошаговые примеры [ править ]

Делимость на 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).

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

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

Если число представляет собой умножение 3 идентичных последовательных цифр в любом порядке, то это число всегда делится на 3. Это полезно, когда число принимает форму ( n × ( n - 1) × ( n + 1))

Пример.

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)

Пример.

1. 336 (исходный номер)
2. 6 × 7 × 8 = 336
3. 336 ÷ 3 = 112

Делимость на 4 [ править ]

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

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

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

1. 2092 (исходный номер)
2. 20 92 (возьмите две последние цифры номера, отбрасывая все остальные цифры)
3. 92 ÷ 4 = 23 (проверьте, делится ли число на 4)
4. 2092 ÷ 4 = 523 (если полученное число делится на 4, то исходное число делится на 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] Это лучший тест для использования.

Если число делится на шесть, возьмите исходное число (246) и разделите его на два (246 ÷ 2 = 123). Затем возьмите этот результат и разделите его на три (123 ÷ 3 = 41). Этот результат совпадает с исходным числом, деленным на шесть (246 ÷ 6 = 41).

Пример.

Общее правило

1. 324 (исходный номер)
2. 324 ÷ 3 = 108 (проверьте, делится ли исходное число на 3)
3. 324 ÷ 2 = 162 ИЛИ 108 ÷ 2 = 54 (проверьте, делится ли исходное число или результат предыдущего уравнения на 2)
4. 324 ÷ 6 = 54 (Если любой из тестов на последнем шаге верен, то исходное число делится на 6. Кроме того, результат второго теста возвращает тот же результат, что и исходное число, деленное на 6)

Нахождение остатка от деления числа на 6

(1, −2, −2, −2, −2 и −2 продолжаются для остальных) Нет периода. - Минимальная величина последовательности

(1, 4, 4, 4, 4 и 4 продолжаются для остальных) - Положительная последовательность

Умножьте самую правую цифру на самую левую цифру в последовательности и умножьте вторую самую правую цифру на вторую самую левую цифру в последовательности и так далее.

Затем вычислите сумму всех значений и возьмите остаток от деления на 6.

Пример: каков остаток от деления 1036125837 на 6?

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

Умножение второй крайней правой цифры = 3 × −2 = −6

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

Четвертая правая цифра = −10

Пятая правая цифра = −4

Крайняя правая шестая цифра = −2

Седьмая правая цифра = −12

Крайняя восьмая цифра = −6

Крайняя правая девятая цифра = 0

Самая правая десятая цифра = −2

Сумма = −51

−51 ≡ 3 (мод. 6)

Остаток = 3

Делимость на 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. Итак, прибавьте пять раз последнюю цифру к числу, образованному оставшимися цифрами, и продолжайте делать это до тех пор, пока получается число, для которого известно, делится ли оно на 7. ^[8]

Другой метод - умножение на 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, .. . (мод 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). ^[9]

Этот метод можно упростить, убрав необходимость умножать. Все, что потребуется для этого упрощения, - это запомнить приведенную выше последовательность (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, прибавьте произведение к следующей цифре слева. Запишите результат в строку под этой цифрой. Повторите этот метод умножения цифры единиц на пять и прибавления этого произведения к числу десятков. Добавьте результат к следующей цифре слева. Запишите результат под цифрой. Продолжайте до конца. Если конечный результат равен нулю или кратен семи, тогда да, число делится на семь. В противном случае это не так. Это следует ведическому идеалу - однострочной записи.^{[10] [ ненадежный источник? ]}

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

Делится ли 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 цифр, которые образуют шестизначные числа (допускаются начальные нули), поскольку все такие числа делятся на семь. Например:

001001 = 1001/7 = 143010 010 = 10 010/7 = 1430011 011 = 11 011/7 = 1573100 100 = 100 100/7 = 14 300101 101 = 101 101/7 = 14 443110 110 = 110 110/7 = 15 730

01 01 01 = 10 101/7 = 144310 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. Это легко сделать, добавив цифры слева от от первых шести до последних шести и следуйте шагу А.

Шаг 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 оставляет остаток от 6 при делении на 7.

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

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

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

1 мод 7 = 1

100 мод 7 = 2

10,000 мод 7 = 2 ^ 2 = 4

1000000 мод 7 = 2 ^ 3 = 8; 8 мод 7 = 1

10,0000,000 по модулю 7 = 2 ^ 4 = 16; 16 мод 7 = 2

1 000 000 000 000 mod 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}})}$

Делимость на 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.

За 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, можно использовать следующий метод. ^[11] Найдите любое число, кратное D, оканчивающееся на 9. (Если D заканчивается соответственно на 1, 3, 7 или 9, тогда умножьте на 9, 3, 7 или 1.) Затем добавьте 1 и разделите на 10, обозначая результат как м . Тогда число N = 10 т + д делится на D тогда и только тогда , когда MQ + T делится на D . Если число слишком велико, вы также можете разбить его на несколько строк по e цифр в каждой, удовлетворяя либо 10 ^e = 1, либо 10.^е = -1 (по модулю 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, так что НОД (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 года ^[12].

Доказательства [ править ]

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

Многие из более простых правил можно создать, используя только алгебраические манипуляции, создавая биномы и переставляя их. Записывая число как сумму каждой цифры, умноженной на степень 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 множители 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.

См. Также [ править ]

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

Ссылки [ править ]

Источники [ править ]

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

Внешние ссылки [ править ]

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