Системы счисления.

[NL0]

Помогите, пожалуйста, разобраться.

Сформулировать и доказать признак делимости на $7$ и на $11$ в $21$-ричной системе счисления.


Представим наше число в таким образом:

$x = \displaystyle\sum_{k=0}^{n-1} a_k 21^k$, где $0 \leqslant a_k \leqslant 20$

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

А вот с делением на $11$ сложнее. Остаток от деления на 11 у $21^k$ равен $10^k$. Пока что больше не знаю -- в какую сторону думать.

[mihaild]

NL0 в сообщении #1139305 писал(а):

Остаток от деления на 11 у $21^k$ равен $10^k$

Остаток от деления по определению меньше делителя. Чему равно $10^k \mod 11$? (подсказка: $10 \equiv -1\ (\mod 11)$)

[DeBill]

NL0 в сообщении #1139305 писал(а):

на $7$ делится любое число, у которого последняя цифра ноль

Или 7. Или ....

[svv]

Е

[Батороев]

NL0 в сообщении #1139305 писал(а):

А вот с делением на $11$ сложнее. Остаток от деления на 11 у $21^k$ равен $10^k$. Пока что больше не знаю -- в какую сторону думать.

Вспомните признак делимости на $11$ для десятичной системы и попробуйте провести аналогию.

-- 21 июл 2016 22:54 --

В общем случае, подумайте, как можно хитро перевести число, записанное в $n$-чной системе в $(n+1)$-чную.

[NL0]

DeBill в сообщении #1139318 писал(а):

NL0 в сообщении #1139305 писал(а):

на $7$ делится любое число, у которого последняя цифра ноль

Или 7. Или ....

Действительно, получается, что в разложении $x = \displaystyle\sum_{k=0}^{n-1} a_k 21^k$ должно $a_0$ делиться на $7$. Получается, что последние две цифры должны делиться на $7$, верно?

mihaild в сообщении #1139312 писал(а):

Остаток от деления по определению меньше делителя. Чему равно $10^k \mod 11$? (подсказка: $10 \equiv -1\ (\mod 11)$)

Выходит $10^k \equiv (-1)^k\ (\mod 11)$

А значит остаток признак можно сформулировать аналогично обычному десятиричному.

$x = \displaystyle\sum_{k=0}^{n-1} a_k 21^k$ делится на $11$, когда $\displaystyle\sum_{k=0}^{n-1} (-1)^k a_k$ делится на $11$. Иными словами сумма цифр с чередующимися знаками должна делится на $11$, верно?

-- 22.07.2016, 00:39 --

Батороев в сообщении #1139321 писал(а):

В общем случае, подумайте, как можно хитро перевести число, записанное в $n$-чной системе в $(n+1)$-чную.

$x = \displaystyle\sum_{k=0}^{n-1} a_k b^k=\displaystyle\sum_{k=0}^{m-1} c_k (b+1)^k$

$\displaystyle\sum_{k=0}^{n-1} a_k b^k=\displaystyle\sum_{k=0}^{m-1} c_k \sum_{i=0}^{l}C_{l}^ib^i$

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

[svv]

NL0 в сообщении #1139382 писал(а):

получается, что в разложении $x = \displaystyle\sum_{k=0}^{n-1} a_k 21^k$ должно $a_0$ делиться на $7$. Получается, что последние две цифры должны делиться на $7$, верно?

Почему две? Эта самая $a_0$ и должна. А происходит это тогда, когда она либо 0, либо 7, либо E (по-нашему 14).

Вы, вероятно, не поняли, что в 21-ричной системе каждое $a_k$ из разложения записывается одной цифрой. Ведь в этой системе различных цифр — двадцать одна. Их разумно обозначить:
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K.
Если последняя цифра $a_0$ числа $x$ — одна из трёх, отмеченных синеньким, число делится на 7. Нет — нет.

[NL0]

Спасибо, понятно, действительно, я забыл, что дальше идут буквы...

А с делимостью на $11$ правильно?

[Батороев]

NL0 в сообщении #1139382 писал(а):

это не хитро, а просто в лоб))

Я к сожалению пропустил мимо глаз сообщение mihaild и фактически продублировал его.
А "хитрая" запись - это: $10_{n}=(10-1)_{n+1}$.

[svv]

NL0 в сообщении #1139382 писал(а):

Выходит $10^k \equiv (-1)^k\ (\mod 11)$

А значит остаток признак можно сформулировать аналогично обычному десятиричному.

$x = \displaystyle\sum_{k=0}^{n-1} a_k 21^k$ делится на $11$, когда $\displaystyle\sum_{k=0}^{n-1} (-1)^k a_k$ делится на $11$. Иными словами сумма цифр с чередующимися знаками должна делится на $11$, верно?

Признак верный, но не уверен, что Вы пришли к нему правильным путём. Я буду использовать нотацию, принятую в программировании: $a\operatorname{mod}b$ — это остаток от деления $a$ на $b$.

В $21$-ричной системе значения $10^k\operatorname{mod}11$ Вам не нужны. Нужны значения $21^k\operatorname{mod}11$. Они равны $1$ для четных $k$ и $10$ для нечётных. Соответственно, работать с ними неудобно — кому охота умножать? Выход в том, чтобы искать не $x\operatorname{mod}11$, а $x\operatorname{mod}22$. Поскольку $21^k \equiv (-1)^k(\operatorname{mod} 22)$, мы для делимости на $22$ в $21$-ричной системе получаем такое же правило, как для делимости на $11$ в десятичной. Но так как нас интересует делимость на $11$, «подходящим» следует считать остаток не только 0, но и B (т.е. одиннадцать).

[NL0]

Спасибо, Ваш вывод вроде понял, но разве нельзя было так?

$21 \equiv -1\ (\mod 11)$, значит $21^k \equiv (-1)^k\ \pmod {11}$

Значит $ \displaystyle\sum_{k=0}^{n-1} a_k 21^k\equiv \displaystyle\sum_{k=0}^{n-1} (-1)^k a_k \pmod {11}$

Отсюда и следует признак сходимости, разве это неверно?

(Оффтоп)

Спасибо, поправил сравнение по модулю

[arseniiv]

(mod)

cepesh в сообщении #443191 писал(а):

Как записать сравнение по модулю или остаток от деления?
Чтобы записать сравнение по модулю, используйте \pmod{модуль}:

$$2 \equiv 5 \pmod 3$$ $$0 \not\equiv \frac{\pi}2 \pmod{2\pi}$$

Используется синтаксис LaTeX

$$2 \equiv 5 \pmod 3$$
$$0 \not\equiv \frac{\pi}2 \pmod{2\pi}$$

Если скобки вокруг $\operatorname{mod} 3$ не нужны, просто \mod:

$$2 \equiv 2 \mod 1$$

Используется синтаксис LaTeX

$$2 \equiv 2 \mod 1$$

Чтобы обозначить взятие остатка, пишите \bmod:

$$5 \bmod 3 = 2$$

Используется синтаксис LaTeX

$$5 \bmod 3 = 2$$

Обратите внимание, что \pmod и \bmod дают разные отступы.

[svv]

NL0
Да, я Вас понял, очень хорошо.
Я сначала ошибочно подумал, что Вы непосредственно формулу для десятичной системы применили к 21-ричной.