Представляя целое число n в системе счисления с основанием 12, вывести признаки делимости на 5.
Походу число будет делиться на 5, если оно заканчивается нулем или пятеркой. Выводится тем, что число можно представить в виде 10a + c, где с - это цифра единиц в записи самого числа. Но надо как то через сравнения. Помогите, пожалуйста, решить.

задан 26 Июл '13 0:51

изменен 29 Июл '13 12:32

Deleted's gravatar image


126

Мне кажется, здесь речь идёт, скорее всего, вот о каком признаке. Про число, записанное в десятичной системе, мы всё и так знаем про делимость на 5, и там нечего анализировать. Но пусть теперь у нас есть система счисления с основанием 12, цифрами которой можно считать 0, 1, 2, ..., 9, a, b. И пусть число $%n$% записано именно в этой системе -- например, его цифры $%4aa9b7$%. Тут сходу не видно, делится ли оно на $%5$%, и задача может состоять в том, как это быстро сделать, зная 12-ичные (но не десятичные!) цифры числа. Это я пытаюсь уточнить условие.

(26 Июл '13 1:04) falcao

Точно, Вы правы. Забыл я уже системы счисления... Как это сделать - не понимаю.

(26 Июл '13 1:15) IviBring
10|600 символов нужно символов осталось
1

Пусть число $%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

Огромное спасибо.

(26 Июл '13 16:28) IviBring
10|600 символов нужно символов осталось
0

@falcao, спасибо большое! Ваши решения на этом форуме очень сильно помогают. Хотелось бы уточнить. А если в данной задаче рассматривать признак делимости на 2, 3, 4, 6. Получается, что во всех этих случаях последняя цифра a_0 числа должна делиться на 2, 3, 4, 6?

ссылка

отвечен 4 Июн 15:39

@olga5: конечно, если мы рассматриваем систему с основанием g, и речь идёт о признаке делимости на d, где d делит g (как в случае с делимостью на 2 и на 5 в десятичной системе), то работает критерий "по последней цифре". Это очевидно, потому что число равно gq+a, где a -- последняя цифра. Первое слагаемое делится на d, и его можно "списать".

(4 Июн 16:09) falcao

@falcao, Вы очень сильный математик!

(4 Июн 16:14) olga5
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×570
×477

задан
26 Июл '13 0:51

показан
1196 раз

обновлен
4 Июн 16:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru