Представляя целое число n в системе счисления с основанием 12, вывести признаки делимости на 5. задан 26 Июл '13 0:51 IviBring |
Пусть число $%n$% записано в системе счисления с основанием $%12$%. Обозначим его цифры, читаемые справа налево, через $%a_0$%, $%a_1$%, $%a_2$%, и так далее. Тогда, по определению позиционной записи числа в системах счисления, имеет место равенство $$n=a_0+12a_1+12^2a_2+12^3a_3+12^4a_4+\cdots\,.$$ Нас интересует значение $%n$% по модулю $%5$% (то есть его остаток от деления на $%5$%); в частности, случай, когда этот остаток равен нулю. Для анализа этой ситуации заметим, что $%12\equiv2\pmod5$%. Из свойств сравнений следует, что это же верно для всех степеней, то есть $%12^k\equiv2^k\pmod5$% при всех целых неотрицательных $%k$%. Таким образом, $$n\equiv a_0+2a_1+2^2a_2+2^3a_3+2^4a_4+\cdots\pmod5.$$ Теперь надо понять, как ведут себя степени двойки по модулю $%5$%. Последовательность остатков является периодической, как это всегда бывает в таких случаях. Конкретно: $%2^0\equiv1\pmod5$%, $%2^1\equiv2\pmod5$%, $%2^2\equiv4\equiv-1\pmod5$%, $%2^3\equiv-2\pmod5$%, $%2^4\equiv1\pmod5$%, и далее всё периодически повторяется. Таким образом, степени двойки из предыдущего равенства можно заменить на числа $%1,2,-1,-2$% с последующим периодическим повторением: $$n\equiv (a_0+2a_1-a_2-2a_3)+(a_4+2a_5-a_6-2a_3)+\cdots\pmod5.$$ Фактически, это и есть требуемый признак делимости. Его можно применить, например, к тому числу, цифры которого у меня были выписаны в качестве случайно взятого примера: $%\overline{4aa9b7}$%. Понятно, каковы здесь цифры, и их для удобства можно сразу заменить их остатками от деления на $%5$%, то есть на $%4,0,0,4,1,2$% в том порядке, в котором они идут. Далее подставим их в формулу выше, беря их сумму с коэффициентами $%1,2,-1,-2,\ldots$%, читая их справа налево. Получится $$1\cdot2+2\cdot1-1\cdot4-2\cdot0+1\cdot0+2\cdot4\equiv3\pmod5.$$ Значит, наше число при делении на $%5$% даёт в остатке $%3$%. отвечен 26 Июл '13 2:12 falcao Огромное спасибо.
(26 Июл '13 16:28)
IviBring
|
@falcao, спасибо большое! Ваши решения на этом форуме очень сильно помогают. Хотелось бы уточнить. А если в данной задаче рассматривать признак делимости на 2, 3, 4, 6. Получается, что во всех этих случаях последняя цифра a_0 числа должна делиться на 2, 3, 4, 6? отвечен 4 Июн '17 15:39 olga5 @olga5: конечно, если мы рассматриваем систему с основанием g, и речь идёт о признаке делимости на d, где d делит g (как в случае с делимостью на 2 и на 5 в десятичной системе), то работает критерий "по последней цифре". Это очевидно, потому что число равно gq+a, где a -- последняя цифра. Первое слагаемое делится на d, и его можно "списать".
(4 Июн '17 16:09)
falcao
|
Мне кажется, здесь речь идёт, скорее всего, вот о каком признаке. Про число, записанное в десятичной системе, мы всё и так знаем про делимость на 5, и там нечего анализировать. Но пусть теперь у нас есть система счисления с основанием 12, цифрами которой можно считать 0, 1, 2, ..., 9, a, b. И пусть число $%n$% записано именно в этой системе -- например, его цифры $%4aa9b7$%. Тут сходу не видно, делится ли оно на $%5$%, и задача может состоять в том, как это быстро сделать, зная 12-ичные (но не десятичные!) цифры числа. Это я пытаюсь уточнить условие.
Точно, Вы правы. Забыл я уже системы счисления... Как это сделать - не понимаю.