#11 Digits, Bases and Decimal Periods

Expand the number: \(N=a_rb^r+\cdots+a_1b+a_0\). Since \(b\equiv1\pmod{b-1}\), every power \(b^i\) is congruent to \(1\), so \(N\equiv a_0+\cdots+a_r\pmod{b-1}\).

For \(\overline{312}_b\), the digit sum is \(6\). Thus we need \(b-1\mid6\). Since \(b>5\), \(b-1\ge5\), so the only possibility is \(b-1=6\). The answer is \(b=7\).

If \(N=\overline{a_ra_{r-1}\ldots a_0}\), then \(10^i\equiv(-1)^i\pmod{11}\). Hence \(N\equiv a_0-a_1+a_2-\cdots+(-1)^r a_r\pmod{11}\).

For \(\overline{ab37}\), the condition is \(a-b+3-7=a-b-4\equiv0\pmod{11}\). Since \(1\le a\le9\) and \(0\le b\le9\), we must have \(a-b-4=0\) or \(-11\). Thus \(a=b+4\) for \(b=0,1,2,3,4,5\), or \(a=b-7\) for \(b=8,9\). The numbers are \(4037,5137,6237,7337,8437,9537,1837,2937\).

Let \(N=1000q+r\), where \(0\le r<1000\) is the number formed by the last three digits. Since \(1000\) is divisible by \(8\), we have \(N\equiv r\pmod8\).

For \(\overline{45c2}\), the last three digits form \(502+10c\). We need \(502+10c\equiv0\pmod8\), or \(6+2c\equiv0\pmod8\). Thus \(2c\equiv2\pmod8\), so \(c\equiv1\pmod4\). The answer is \(c=1,5,9\).

We have \(\overline{31}_b=3b+1\). The condition \(5\mid3b+1\) gives \(3b\equiv-1\equiv4\pmod5\). Since \(3^{-1}\equiv2\pmod5\), we get \(b\equiv8\equiv3\pmod5\). With \(b>6\), the answer is all \(b=5t+3\), where \(t\ge1\).

Let the palindrome have \(2r\) digits: \(a_{2r-1}\ldots a_1a_0\), with \(a_i=a_{2r-1-i}\). In the alternating sum for divisibility by \(11\), symmetric digits have opposite signs because their positions have opposite parity. Hence each pair cancels, the whole sum is \(0\), and the number is divisible by \(11\).

If \(m\mid n\), then \(10^m-1\mid10^n-1\), hence \(R_m\mid R_n\).

Conversely, suppose \(R_m\mid R_n\). Then \(10^m-1=9R_m\) divides \(9R_n=10^n-1\). Write \(n=qm+r\), where \(0\le r0\), then \(10^r-1\) is positive and smaller than \(10^m-1\), so it cannot be divisible by \(10^m-1\). Therefore \(r=0\), so \(m\mid n\).

If \(k=ab\), where \(a,b>1\), then

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

Both factors are greater than \(1\), so \(R_k\) is composite. This is a contradiction. Hence \(k\) is prime.

Since \(R_3=111=3\cdot37\), if \(3\mid n\), then \(R_3\mid R_n\), so \(37\mid R_n\).

Conversely, \(37\mid R_n\) is equivalent to \(10^n\equiv1\pmod{37}\), because \(9\) is invertible modulo \(37\). The order of \(10\) modulo \(37\) is \(3\): \(10^3=1000\equiv1\pmod{37}\), while \(10\not\equiv1\) and \(10^2=100\not\equiv1\pmod{37}\). Therefore \(3\mid n\).

The answer is all multiples of \(3\).

In long division, each new remainder is obtained by multiplying the previous one by \(10\) modulo \(n\). After \(h\) steps, the initial remainder \(a\) becomes congruent to \(a10^h\pmod n\). A period of length \(h\) means returning to the same remainder: \(a10^h\equiv a\pmod n\). Since \((a,n)=1\), we may cancel \(a\), obtaining \(10^h\equiv1\pmod n\). The least such \(h\) is the period length.

For \(7\): \(10\equiv3\), \(10^2\equiv2\), \(10^3\equiv6\), and \(10^6\equiv1\pmod7\); no smaller positive power gives \(1\). The period is \(6\).

For \(13\): \(10^2\equiv9\), \(10^3\equiv12\equiv-1\pmod{13}\), so \(10^6\equiv1\), and no smaller positive power works. The period is \(6\).

For \(37\): \(10^3=1000\equiv1\pmod{37}\), while \(10\) and \(10^2\) are not congruent to \(1\). The period is \(3\).

Let \(n\) have \(k\) digits. Then \(0.\overline{n}=\frac{n}{10^k-1}\), so the condition gives \(\frac1n=\frac{n}{10^k-1}\), hence \(n^2=10^k-1\).

If \(k=1\), then \(n^2=9\), so \(n=3\). If \(k\ge2\), then \(10^k\) is divisible by \(4\), so \(10^k-1\equiv3\pmod4\), but no square is congruent to \(3\pmod4\). Thus there are no other solutions. The answer is \(n=3\).

The order of \(10\) modulo \(n\) must be \(2\). Hence \(n\mid10^2-1=99\), but \(n\nmid10-1=9\). The divisors of \(99\) are \(1,3,9,11,33,99\). Excluding \(1\) and the divisors of \(9\), we get \(11,33,99\). For each of them, \(10^2\equiv1\pmod n\) while \(10\not\equiv1\pmod n\), so the period is exactly \(2\).

We have \(N=1000\overline{abc}+\overline{abc}=1001\overline{abc}\). But \(1001=7\cdot11\cdot13\). Therefore \(N\) is divisible by \(7\), \(11\), and \(13\).

The condition is \(x(x-1)\equiv0\pmod{100}\). Since \(100=4\cdot25\), with coprime factors, we choose \(x\equiv0\) or \(1\pmod4\) and \(x\equiv0\) or \(1\pmod{25}\). The four systems give:

\(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\).

The answer is \(00,01,25,76\).

The condition that the square ends with the same \(k\) digits is \(x^2\equiv x\pmod{10^k}\), or \(x(x-1)\equiv0\pmod{10^k}\). Since \(10^k=2^k5^k\), and \(x\) and \(x-1\) are coprime, the full powers \(2^k\) and \(5^k\) must be assigned to one of the two consecutive factors.

For example, the system \(x\equiv0\pmod{2^k}\), \(x\equiv1\pmod{5^k}\) has a unique solution modulo \(10^k\) by CRT. It is not simultaneously \(0\) and \(1\). For different large \(k\), these give new nonzero, non-one residues; otherwise one fixed integer would satisfy \(x^2\equiv x\pmod{10^k}\) for infinitely many \(k\), which is possible only for \(x=0\) or \(x=1\). Hence there are infinitely many automorphic numbers.

Let \(P=ab\), and suppose \(P\) has \(k\) digits. Then \(0.\overline{P}=\frac{P}{10^k-1}=\frac{ab}{10^k-1}\). The condition gives \(\frac{a}{b}=\frac{ab}{10^k-1}\). Since \(a>0\), cancel \(a\): \(\frac1b=\frac{b}{10^k-1}\), so \(b^2=10^k-1\).

For \(k=1\), this gives \(b=3\). For \(k\ge2\), \(10^k-1\equiv3\pmod4\), but no square is congruent to \(3\pmod4\). Therefore \(b=3\). Since the fraction is proper and reduced, \(a=1\) or \(a=2\). The answer is \(\frac13\) and \(\frac23\).

If \(M=B_0+B_1 10^k+B_2 10^{2k}+\cdots+B_s10^{sk}\), where the \(B_i\) are the blocks, then modulo \(10^k-1\) each power \(10^{ik}\) is congruent to \(1\). Hence \(M\equiv B_0+B_1+\cdots+B_s=T(M)\pmod{10^k-1}\).

Also, the digit sum of \(T(M)\) is not greater than the digit sum of \(M\): carries during addition can only decrease the digit sum. If \(M\ge10^k\), then \(T(M)

Choose \(k\) such that \(9k\ge A\), and set \(B=10^k-1\). If \(n\ge B\), then \(10^k-1\) is one of the factors in \(1\cdot2\cdots n=n!\). Therefore \(10^k-1\mid n!\).

By the previous block estimate, every positive multiple of \(10^k-1\) has digit sum at least \(9k\). Hence the digit sum of \(n!\) is at least \(9k\), and therefore at least \(A\).

Period exactly \(3\) means that the order of \(10\) modulo \(n\) is \(3\). Hence \(n\mid10^3-1=999\), but \(n\nmid10-1=9\). Since \(999=3^3\cdot37\), the relevant divisors must contain the factor \(37\). They are \(37,3\cdot37,9\cdot37,27\cdot37\), namely \(37,111,333,999\).

For each of them, \(10^3\equiv1\pmod n\), while \(10\not\equiv1\pmod n\), because \(37\mid n\) but \(37\nmid9\). Thus the period is indeed \(3\). The answer is \(37,111,333,999\).

From \(p\mid R_q\), we get \(10^q\equiv1\pmod p\), because \(9R_q=10^q-1\). Since \(p\ne3\), there is no exceptional division by \(9\); also \(p\ne2,5\). Let \(d\) be the order of \(10\) modulo \(p\). Then \(d\mid q\). Since \(q\) is prime, \(d=1\) or \(d=q\).

If \(d=1\), then \(10\equiv1\pmod p\), so \(p\mid9\), hence \(p=3\), which is excluded. Therefore \(d=q\). By the order theorem, \(d\mid p-1\), so \(q\mid p-1\), i.e. \(p\equiv1\pmod q\).