Материал о сравнении по модулю m также новый в программе для старших классов и поэтому подробно описан в учебнике. Введено понятие сравнения по модулю m и соответствующее обозначение, сформулированы четыре свойства сравнений. Рассмотренная теория применена для доказательства делимости 622 − 1 на 7, нахождения остатка от деления 229 на 11, доказательства признака делимости на 9.
Решения и комментарии
1.92. Сформулируйте признак делимости на 11 и докажите его.
Сформулируем признак делимости на 11:
если разность суммы цифр числа, стоящих на четных местах, и суммы цифр, стоящих на нечетных местах, делится на 11, то и число делится на 11.
Верно и обратное утверждение:
если число делится на 11, то разность суммы его цифр, стоящих на четных местах, и суммы цифр, стоящих на нечетных местах, делится на 11.
Доказательство. Так как 10≡−1( mod11 ) , то 10 2n ≡ ( −1 ) 2n ( mod11 )≡1( mod11 ) , а 10 2n+1 ≡ ( −1 ) 2n+1 ( mod11 )≡−1( mod11 ) .
Рассмотрим доказательство признака делимости на 11 на примере шестизначного натурального числа a 6 a 5 a 4 a 3 a 2 a 1 a 0 ¯ . Для него справедливы сравнения:
a 6 a 5 a 4 a 3 a 2 a 1 a 0 ¯ = a6106 + а5105 + a4104 + a3103 + а2102 + a110 + а0 ≡
≡ а6(−1)6 + а5(−1)5 + a4(−1)4 + а3(−1)3 + a2(−1)2 + a1(−1) + a0(mod 11) ≡
≡ a6 − a5 + a4 − a3 + a2 − а1 + а0 (mod 11) =
= (а6 + а4 + а2 + а0) − ( а5 + а3 + а1). (1)
Справедливость обоих утверждений следует из равенства (1).
1.95. Определите остаток от деления числа 325 на: а) 10; б) 11; в) 13.
Решение. а) Так как 3 2 =9≡−1( mod10 ) , то 3 25 = ( 3 2 ) 12 ⋅3≡ ( −1 ) 12 ⋅3( mod10 )=3 . Следовательно, 3 — остаток от деления числа 325 на 10.
б) Так как 3 5 =243=22⋅11+1≡1( mod11 ) , то 3 25 = ( 3 5 ) 5 ≡ 1 5 ( mod11 )=1 . Следовательно, 1 — остаток от деления числа 325 на 11.
в) Так как 3 3 =27=2⋅13+1≡1( mod13 ) , то 3 25 = ( 3 3 ) 8 ⋅3≡3( mod13 ) . Следовательно, 3 — остаток от деления числа 325 на 13.
1.96. Не выполняя деления, определите остаток от деления числа 200420052006200720082009 на 9.
Решение. 200420052006200720082003 — наибольшее число, не превосходящее данного и делящееся на 9, оно на 6 меньше данного, поэтому 200420052006200720082009 ≡ 6 (mod 9). Следовательно, 6 — остаток от деления данного числа 200420052006200720082009 на 9.
1.97. Пусть Р3(х) = х3− 4х2 + 5х + 1. Определите последнюю цифру числа Р3(102005).
Решение. Так как 10 2005 ≡0( mod10 ) ,
то P 3 ( 10 2005 )≡ P 3 ( 0 )( mod10 ) = 03 − 4 · 02 + 5 · 0 + 1 = 1.
Следовательно, при делении числа Р3(102005) на 10 получается остаток 1, а это означает, что последняя цифра числа P3(102005) (в его десятичной записи) есть 1.
1.98. Пусть Р2004(x) = x2004 − x2003 + x2002 − x2001 ... − х + 1. Определите последнюю цифру числа P2004(1002005).
Решение. Так как 100 2005 ≡0( mod10 ) ,
то P 2004 ≡( 100 2005 )≡ P 2004 ( 0 )( mod10 ) = 02004 − 02003 + 02002 − 02001 ... − 0 + 1 = 1. Следовательно, при делении числа Р2004(1002005) на 10 получается остаток 1, а это означает, что последняя цифра числа Р2004(1002005) (в его десятичной записи) есть 1.
1.99. Докажите, что квадрат любого натурального числа либо делится на 9, либо при делении на 3 дает остаток 1.
Доказательство. Любое натуральное число п при делении на 3 дает только один из трех остатков: 0, 1, 2. Поэтому возможен лишь один из трех случаев: 1) n≡0( mod3 ) ; 2) n≡1( mod3 ) ; 3) n≡2( mod3 ) .
1) Если n≡0( mod3 ) , то п = 3m, где m∈ N. Тогда п2 = 9m2, т. е. n2 делится на 9.
2) Если n≡1( mod3 ) , то n 2 ≡ 1 2 ( mod3 )≡1( mod3 ) , т. е. n2 при делении на 3 дает остаток 1.
3) Если n≡2( mod3 ) , то n 2 ≡4( mod3 )≡1( mod3 ) , т. е. n2 при делении на 3 дает остаток 1.
Таким образом, утверждение полностью доказано.
1.100. Найдите последнюю цифру числа 9 9 9 .
Решение. Так как число 99 = 2n + 1, где n∈ N и 9≡−1( mod10 ) , то 9 2n+1 ≡−1( mod10 )≡9( mod10 ) . Следовательно, при делении числа 9 9 9 на 10 получится остаток 9, а это означает, что 9 — последняя цифра числа 9 9 9 . |
