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

Рассмотренные свойства отношения делимости позволяют доказать известные признаки делимости чисел, записанных в десятич­ной системе счисления, на 2, 3, 4, 5, 9.

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

Теорема (признак делимости на 2). Для того чтобы число x делилось на 2, необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр 0, 2, 4, 6, 8.

Доказательство. Пусть число х записано в десятичной системе счисления, т.е.

 , где  принимают значения 0,1,2, 3, 4, 5, 6, 7, 8, 9, ап  0 и а0 принимает значе­ния 0, 2, 4, 6, 8. Докажем, что тогда х 2.

Так как 102, то 102 2, 103  2, ... , 10n  2 и, значит, ()2. По условию а0 тоже делится на 2, и поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, чис­ло х делится на 2.

Докажем обратное: если число х делится на 2, то его десятичная запись оканчивается одной из цифр 0, 2, 4, 6, 8.

Запишем равенство в таком ви­де:    а0 = . Но тогда, по теореме о дели­мости разности, а02, поскольку х2 и () 2. Чтобы однозначное число а0 делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

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

Доказательство этого признака аналогично доказательству при­знака делимости на 2.

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

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

Так как 1004, то ()4. По условию,    (это и есть запись двузначного числа) также делится на 4. Поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 4. Следовательно, согласно признаку делимости суммы, и само число х делится на 4.

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

Запишем равенство  в таком виде:  = х - (). Так как х4 и ()4, то по теореме о делимости разности () 4. Но выражение  есть запись двузначного числа, образованного последними цифрами записи числах.

Например, число 157872 делится на 4. так как последние две цифры в его записи образуют число 72, которое делится на 4. Число 987641 не делится на 4, так как последние две цифры в его записи образуют чис­ло 41, которое не делится на 4.

Теорема (признак делимости на 25). Для того чтобы число х делилось на 25, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 00, 25,50 или 75.

Доказательство аналогично признаку делимости на 4.

Теорема (признак делимости на 9). Для того чтобы число x де­лилось на 9. необходимо и достаточно, чтобы сумма цифр его десятич­ной записи делилась на 9.

Доказательство. Докажем сначала, что числа вида 10n - 1 делятся на 9. Действительно, 10n - 1 = (9*10n-1 + 10n-1) - 1 = (9*10n-1  +  9*10n-2 + 10n-2) - 1 = (9*10n-1  +  9*10n-2  + ... + 10) - 1 = 9*10n-1 +  9*10n-2 + ... + 9. Каждое слагаемое полученной суммы делится на 9, значит, и число 10n - 1 делится на 9.

Пусть число х = an*10n + an-1* 10n-1 + ... + a1*10 + a0 и (an + an-1+ ... + а1 + а0) 9. Докажем, что тогда x 9.

Преобразуем сумму an*10n + an-1* 10n-1 + ... + a1*10 + a0 прибавив и вычтя из нее выражение an + an-1+ ... + а1 + а0 и записав результат в таком виде: x = (an* 10n - an) + (an-1*10n-1 – аn-1) + ... + (a1*10 + a1) + + (a0 + a0) + (an + an-1+ ... + а1 + а0 = аn (10n - 1) + an-1(10n-1-1) + ... + a1(10- 1) + (an + an-1+ ... + а1 + а0).

В последней сумме каждое слагаемое делится на 9:

аn (10n - 1)  9, так как (10n - 1)  9,

an-1(10n-1-1)  9, так как (10n-1-1)  9 и т.д.

a1(10- 1)   9, так как (10- 1)  9,

(an + an-1+ ... + а1 + а0)  9 по условию.

Следовательно, x  9.

Докажем обратное, т.е. если x  9, то сумма цифр его десятичной записи делится на 9.

Равенство х = an + an-1 + ... + а1 + а0 запишем в та­ком виде: an + an-1+ ... + а1 + а0= x - (аn (10n - 1) + an-1(10n-1-1) + ... + a1(10- 1)). Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 9, то по теореме о делимости разности (an + an-1+ ... + а1 + а0)  9, т.е. сумма цифр десятичной записи числа x- делится на 9, что и требовалось доказать.

Например, число 34578 делится на 9, так как сумма его цифр, рав­ная 27, делится на 9. Число 130542 не делится 9, так как сумма его цифр, равная 15, не делится на 9.

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

Доказательство этого утверждения аналогично доказательству признака делимости на 9.

Мы рассмотрели признаки делимости чисел на 2, 3, 4, 5, 9. Из школьного курса математики известен еще ряд других, например, на 10 и 25. Конечно, этого недостаточно, чтобы решать вопросы делимости. Существует общий признак делимости для чисел, записанных в любой позиционной системе счисления, открытый в XVII веке французским математиком Паскалем. Мы рассмотрим его для случая, когда осно­ванием системы счисления является число 10.

Теорема (признак делимости Паскаля). Число

х = an*10n + an-1* 10n-1 + ... + a1*10 + a0        (1)

делится на число b тогда и только тогда, когда на b делится сумма an*rn+ an-1*rn-1+…+a1*r1+a0, где r1, r2, …, rn - остатки от деле­ния на b разрядных единиц 10, 102,.... 10n .

Доказательство. Разделим на b каждую из разрядных единиц числа x, получим: 10 = bq1+r1,  102 = bq2+ r2 .... 10n-1 = bqn-1+rn-1 , 10n = bqn+rn  , где q1, q2, …, qn-1, qn - частные, a r1, r2, …, rn-1, rn -остатки.

Подставим в равенство (1) вместо разрядных единиц соответст­вующие выражения и, используя свойства сложения и умножения, выполним преобразования: х = an(bqn+rn ) + an-1 (bqn-1+rn-1) + ... + a1(bq1+r1) + а0 = (anqn + an-1 qn-1+…+ a1q1 )b+ (anrn + an-1 rn-1 + ... + a1r1+ а0). Если сумму anrn + an-1 rn-1 + ... + a1r1+ а0 обозна­чить буквой s, то будем иметь:  х = (anqn + an-1 qn-1+…+ a1q1 )b + s. Разделим s на b: s = bq + r, где 0 < r < b. Тогда х = (anqn + an-1 qn-1+…+ a1q1 )b +( bq + r) =( anqn + an-1 qn-1 +…+ a1q1 + q)b + r. Короче: x= b*Q + r , где Q = anqn + an-1 qn-1 +…+ a1q1 + q и 0 < r < b. Равенство x= b*Q означает, что r является остатком при делении x на b, причем r - число единственное согласно теореме о единственно­сти частного и остатка при делении натуральных чисел. Таким обра­зом, установлено, что при делении натурального числа  х = an*10n + an-1* 10n-1 + ... + a1*10 + a0  на натуральное число b получается такой же остаток r, как и при делении на число b суммы s. Теорема доказана.

Используя признак делимости Паскаля, можно доказать следующий признак делимости чисел на 11: для того, чтобы число делилось на 11, необходимо и достаточно, чтобы разность между суммой его цифр, стоящих на нечетных местах, и суммой цифр, стоящих на четных местах, делилась на 11. Обычно при нахождении разности из большего числа вычитают меньшее. Например, число 540309 делится на 11, так как (4+3+9)–(5+0+0)=11, 11: 11. Число 236 не делится на 11, поскольку (2+6)–3=5, но 5 не кратно 11.

Докажем также следующие утверждения:

1. Произведение двух последовательных натуральных чисел n и n+1 делится на 2.

Решение. Чтобы показать, что произведение n·(n+1) делится на 2, надо рассмотреть две возможности:

1) n делится на 2, т.е. n=2k. Тогда произведение n·(n+1) будет иметь вид: 2k·(2k+1). Это произведение делится на 2, так как первый множитель в нем делится на 2;

2) n не делится на 2, т.е. n=2k+1. Тогда произведение n·(n+1) будет иметь вид: (2k+1)·(2k+2). Это произведение делится на 2, так как второй множитель делится на 2.

2. Произведение трех последовательных натуральных чисел n, n+1, n+2 делится на 3.

Решение. Чтобы показать, что произведение n·(n+1)·(n+2) делится на 3, надо рассмотреть три возможности:

1) n делится на 3, т.е. n=3k. Тогда n·(n+1)·(n+2) будет иметь вид: 3k·(3k+1)·(3k+2). Это произведение делится на 3, так как первый множитель в нем делится на 3;

2) n при делении на 3 дает в остатке 1, т.е. n=3k+1. Тогда произведение n·(n+1)·(n+2) будет иметь вид: (3k+1)·(3k+2)·(3k+3). Это произведение делится на 3, т.к. третий множитель делится на 3;

3) n при делении на 3 дает в остатке 2, т.е. n=3k+2. Тогда произведение n·(n+1)·(n+2) будет иметь вид: (3k+2)·(3k+3)·(3k+4). Это произведение делится на 3, т.к. второй множитель в нем делится на 3.

На основании задач 20 и 21 можно сформулировать утверждение, что произведение трех последовательных натуральных чисел делится на 6.

Рассмотрим задачу. Докажем, что произведение четырех последовательных натуральных чисел n,  n+1, n+2, n+3 делится на 4.

Решение. Чтобы показать, что произведение n·(n+1)·(n+2)·(n+3) делится на 4 надо рассмотреть четыре возможности:

1) n делится на 4, т.е. n=4k. Тогда n·(n+1)·(n+2)·(n+3) будет иметь вид: 4k·(4k+1)·(4k+2)·(4k+3). Это произведение делится на 4, так как первый множитель в нем делится на 4;

2) n при делении на 4 дает в остатке 1, т.е. n=4k+1. Тогда n·(n+1)·(n+2)·(n+3) будет иметь вид: (4k+1)·(4k+2)·(4k+3)·(4k+4). Это произведение делится на 4, так как последний множитель делится на 4;

 3) n при делении на 4 дает в остатке 2, т.е. n=4k+2. Тогда n·(n+1)·(n+2)·(n+3) будет иметь вид: (4k+2)·(4k+3)·(4k+4)·(4k+5). Это произведение делится на 4, так как третий множитель делится на 4;

4) n при делении на 4 дает в остатке 3, т.е. n=4k+3. Тогда n·(n+1)·(n+2)·(n+3) будет иметь вид: (4k+3)·(4k+4)·(4k+5)·(4k+6). Это произведение делится на 4, так как второй множитель делится на 4.

Так как произведение n·(n+1)·(n+2)·(n+3) содержит произведение двух, трех последовательных натуральных чисел, то оно делится на 2 и на 3.