#11 Цифры, системы счисления и десятичные периоды

Разложим число: \(N=a_rb^r+\cdots+a_1b+a_0\). Так как \(b\equiv1\pmod{b-1}\), то каждая степень \(b^i\) сравнима с \(1\), значит \(N\equiv a_0+\cdots+a_r\pmod{b-1}\).

Для \(\overline{312}_b\) сумма цифр равна \(6\). Поэтому нужно и достаточно, чтобы \(b-1\mid6\). При \(b>5\) имеем \(b-1\ge5\), значит единственный вариант \(b-1=6\). Ответ: \(b=7\).

Если \(N=\overline{a_ra_{r-1}\ldots a_0}\), то \(10^i\equiv(-1)^i\pmod{11}\). Значит, \(N\equiv a_0-a_1+a_2-\cdots+(-1)^r a_r\pmod{11}\).

Для \(\overline{ab37}\) получаем условие \(a-b+3-7=a-b-4\equiv0\pmod{11}\). Так как \(1\le a\le9\), \(0\le b\le9\), возможны значения \(a-b-4=0\) или \(-11\). Отсюда \(a=b+4\), где \(b=0,1,2,3,4,5\), или \(a=b-7\), где \(b=8,9\). Получаем числа \(4037,5137,6237,7337,8437,9537,1837,2937\).

Пусть \(N=1000q+r\), где \(0\le r<1000\) — число из последних трёх цифр. Так как \(1000\) делится на \(8\), имеем \(N\equiv r\pmod8\).

Для \(\overline{45c2}\) последние три цифры дают число \(502+10c\). Нужно \(502+10c\equiv0\pmod8\), то есть \(6+2c\equiv0\pmod8\). Получаем \(2c\equiv2\pmod8\), значит \(c\equiv1\pmod4\). Ответ: \(c=1,5,9\).

Имеем \(\overline{31}_b=3b+1\). Условие \(5\mid3b+1\) даёт \(3b\equiv-1\equiv4\pmod5\). Так как \(3^{-1}\equiv2\pmod5\), получаем \(b\equiv8\equiv3\pmod5\). При \(b>6\) ответ: все \(b=5t+3\), где \(t\ge1\).

Пусть палиндром имеет \(2r\) цифр: \(a_{2r-1}\ldots a_1a_0\), причём \(a_i=a_{2r-1-i}\). В чередующейся сумме для делимости на \(11\) симметричные цифры стоят с противоположными знаками, потому что их позиции имеют разную чётность. Поэтому каждая пара взаимно уничтожается, вся сумма равна \(0\), и число делится на \(11\).

Если \(m\mid n\), то \(10^m-1\mid10^n-1\), откуда \(R_m\mid R_n\).

Пусть теперь \(R_m\mid R_n\). Тогда \(10^m-1=9R_m\) делит \(9R_n=10^n-1\). Запишем \(n=qm+r\), где \(0\le r0\), число \(10^r-1\) положительно и меньше \(10^m-1\), значит оно не может делиться на \(10^m-1\). Следовательно, \(r=0\), то есть \(m\mid n\).

Если \(k=ab\), где \(a,b>1\), то

\[R_k=1+10+\cdots+10^{ab-1}=R_a(1+10^a+10^{2a}+\cdots+10^{a(b-1)}).\]

Оба множителя больше \(1\), поэтому \(R_k\) составно. Противоречие. Значит, \(k\) простое.

Так как \(R_3=111=3\cdot37\), то при \(3\mid n\) имеем \(R_3\mid R_n\), значит \(37\mid R_n\).

Обратно, \(37\mid R_n\) равносильно \(10^n\equiv1\pmod{37}\), потому что \(9\) обратимо по модулю \(37\). Проверим порядок \(10\) по модулю \(37\): \(10^3=1000\equiv1\pmod{37}\), а \(10\not\equiv1\), \(10^2=100\not\equiv1\pmod{37}\). Значит, порядок равен \(3\), и \(3\mid n\).

Ответ: все \(n\), кратные \(3\).

При делении в столбик каждый новый остаток получается умножением предыдущего на \(10\) по модулю \(n\). Через \(h\) шагов начальный остаток \(a\) переходит в остаток, сравнимый с \(a10^h\pmod n\). Период длины \(h\) означает возвращение к тому же остатку: \(a10^h\equiv a\pmod n\). Так как \((a,n)=1\), можно сократить на \(a\), получая \(10^h\equiv1\pmod n\). Минимальный такой \(h\) и есть длина периода.

Для \(7\): \(10\equiv3\), \(10^2\equiv2\), \(10^3\equiv6\), \(10^6\equiv1\pmod7\), меньшая положительная степень не даёт \(1\). Период равен \(6\).

Для \(13\): \(10^2\equiv9\), \(10^3\equiv12\equiv-1\pmod{13}\), поэтому \(10^6\equiv1\), а меньшая положительная степень не подходит. Период равен \(6\).

Для \(37\): \(10^3=1000\equiv1\pmod{37}\), а \(10\) и \(10^2\) не сравнимы с \(1\). Период равен \(3\).

Пусть \(n\) имеет \(k\) цифр. Тогда \(0.\overline{n}=\frac{n}{10^k-1}\), поэтому условие даёт \(\frac1n=\frac{n}{10^k-1}\), то есть \(n^2=10^k-1\).

Если \(k=1\), получаем \(n^2=9\), значит \(n=3\). Если \(k\ge2\), то \(10^k\) делится на \(4\), поэтому \(10^k-1\equiv3\pmod4\), а квадрат не может быть сравним с \(3\pmod4\). Следовательно, других решений нет. Ответ: \(n=3\).

Нужно, чтобы порядок \(10\) по модулю \(n\) равнялся \(2\). Значит, \(n\mid10^2-1=99\), но \(n\nmid10-1=9\). Делители \(99\): \(1,3,9,11,33,99\). Исключаем \(1\) и делители \(9\). Остаются \(11,33,99\). Для каждого из них \(10^2\equiv1\pmod n\), но \(10\not\equiv1\pmod n\), значит период действительно равен \(2\).

Имеем \(N=1000\overline{abc}+\overline{abc}=1001\overline{abc}\). Но \(1001=7\cdot11\cdot13\). Поэтому \(N\) делится на \(7\), \(11\) и \(13\).

Условие равно \(x(x-1)\equiv0\pmod{100}\). Так как \(100=4\cdot25\), причём \(4\) и \(25\) взаимно просты, нужно выбрать \(x\equiv0\) или \(1\pmod4\) и \(x\equiv0\) или \(1\pmod{25}\). Получаем четыре системы:

\(x\equiv0\pmod4, x\equiv0\pmod{25}\): \(x\equiv0\).

\(x\equiv1\pmod4, x\equiv1\pmod{25}\): \(x\equiv1\).

\(x\equiv1\pmod4, x\equiv0\pmod{25}\): \(x\equiv25\).

\(x\equiv0\pmod4, x\equiv1\pmod{25}\): \(x\equiv76\).

Ответ: \(00,01,25,76\).

Условие, что квадрат заканчивается теми же \(k\) цифрами, есть \(x^2\equiv x\pmod{10^k}\), то есть \(x(x-1)\equiv0\pmod{10^k}\). Так как \(10^k=2^k5^k\), а \(x\) и \(x-1\) взаимно просты, все множители \(2^k\) и \(5^k\) должны целиком попасть в один из двух соседних множителей.

Например, система \(x\equiv0\pmod{2^k}\), \(x\equiv1\pmod{5^k}\) имеет единственное решение по модулю \(10^k\) по CRT. Оно не равно одновременно \(0\) и \(1\). Для разных больших \(k\) получаются всё новые ненулевые неединичные остатки; иначе одно фиксированное число удовлетворяло бы \(x^2\equiv x\pmod{10^k}\) для бесконечно многих \(k\), что возможно только при \(x=0\) или \(x=1\). Значит, автоморфных чисел бесконечно много.

Пусть \(P=ab\), и пусть \(P\) имеет \(k\) цифр. Тогда \(0.\overline{P}=\frac{P}{10^k-1}=\frac{ab}{10^k-1}\). Условие даёт \(\frac{a}{b}=\frac{ab}{10^k-1}\). Так как \(a>0\), сокращаем на \(a\): \(\frac1b=\frac{b}{10^k-1}\), значит \(b^2=10^k-1\).

При \(k=1\) получаем \(b=3\). При \(k\ge2\) число \(10^k-1\equiv3\pmod4\), а квадрат не бывает сравним с \(3\pmod4\). Следовательно, \(b=3\). Так как дробь правильная и несократимая, \(a=1\) или \(a=2\). Ответ: \(\frac13\) и \(\frac23\).

Если \(M=B_0+B_1 10^k+B_2 10^{2k}+\cdots+B_s10^{sk}\), где \(B_i\) — блоки, то по модулю \(10^k-1\) каждая степень \(10^{ik}\) сравнима с \(1\). Поэтому \(M\equiv B_0+B_1+\cdots+B_s=T(M)\pmod{10^k-1}\).

Кроме того, сумма цифр \(T(M)\) не больше суммы цифр \(M\): при сложении блоков переносы могут только уменьшить сумму цифр. Если \(M\ge10^k\), то \(T(M)

Выберем \(k\) так, чтобы \(9k\ge A\), и положим \(B=10^k-1\). Если \(n\ge B\), то число \(10^k-1\) входит среди множителей произведения \(1\cdot2\cdots n=n!\). Поэтому \(10^k-1\mid n!\).

По предыдущей блоковой оценке всякий положительный кратный \(10^k-1\) имеет сумму цифр не меньше \(9k\). Значит, сумма цифр \(n!\) не меньше \(9k\), а значит, не меньше \(A\).

Период ровно \(3\) означает, что порядок \(10\) по модулю \(n\) равен \(3\). Поэтому \(n\mid10^3-1=999\), но \(n\nmid10-1=9\). Так как \(999=3^3\cdot37\), делители \(999\), не являющиеся делителями \(9\), но дающие порядок \(3\), должны содержать множитель \(37\). Возможны \(37,3\cdot37,9\cdot37,27\cdot37\), то есть \(37,111,333,999\).

Для каждого из них \(10^3\equiv1\pmod n\), а \(10\not\equiv1\pmod n\), потому что \(37\mid n\), но \(37\nmid9\). Значит, период действительно равен \(3\). Ответ: \(37,111,333,999\).

Из \(p\mid R_q\) следует \(10^q\equiv1\pmod p\), поскольку \(9R_q=10^q-1\). При \(p\ne3\) деление на \(9\) не создаёт исключения; кроме того, \(p\ne2,5\). Пусть \(d\) — порядок \(10\) по модулю \(p\). Тогда \(d\mid q\). Так как \(q\) простое, \(d=1\) или \(d=q\).

Если \(d=1\), то \(10\equiv1\pmod p\), значит \(p\mid9\), откуда \(p=3\), что исключено. Следовательно, \(d=q\). По теореме о порядке элемента \(d\mid p-1\), значит \(q\mid p-1\), то есть \(p\equiv1\pmod q\).