今天又是個被問數學的早晨～ 😆
大學同學問我 森棚教官數學題－全數出動，也給了提示 $n=3^r$ 應該是解答。
前置作業
先定義對於每一個 $n$ 我們最少需要 $\mathcal{L}(n)$ 個 $1$，使得 $n\mid\overbrace{1\dots\dots\dots1}^{\mathcal{L}(n)}$。
有一些簡單的特性可以很快看出
- $\mathcal{L}(n)\leq n$。
- 如果正整數 $k$ 也滿足 $n\mid\overbrace{1\dots\dots\dots1}^{k}$，那麼 $\mathcal{L}(n)\mid k$。
- 如果 $n\mid m$ 則 $\mathcal{L}(n)\mid\mathcal{L}(m)$。
- 如果 $n$ 是解答，表示 $\mathcal{L}(n)=n$
然後先把要證明的問題稍微複雜點吧！ 🤓
- $n=3^k$ 是解答且 $\overbrace{1\dots\dots\dots1}^{3^k}$ 恰好有 $k$ 個質因數 $3$。
- 其他數字不滿足。
證明 $n=3^k$
Step 1 : $k=1$
因為 $\mathcal{L}(3)=3$ 所以是解答，且 $111$ 恰好只有 $1$ 個質因數 $3$
Step 2 : 假設 $k=r$ 成立，試證 $k=r+1$ 也成立。
由於 $\overbrace{1\cdots\cdots\cdots1}^{3\mathcal{L}(3^r)}$ 可以寫成 $\overbrace{1\cdots1}^{\mathcal{L}(3^r)}$ 與 $1+10^{\mathcal{L}(3^r)}+10^{2\mathcal{L}(3^r)}$ 的乘積。前者由歸納法得知恰有 $k$ 個質因數 $3$，後者由 倍數檢驗法 知道恰有 $1$ 個質因數 $3$。所以它恰有 $k+1$ 個質因數 $3$，即
於是根據 特性 2 跟 特性 3 知道
所以 $\mathcal{L}(3^{r+1})$ 等於 $\mathcal{L}(3^r)$ 或 $3\mathcal{L}(3^r)$。但根據歸納法知道 $\overbrace{1\dots\dots\dots1}^{3^r}$ 恰好有 $r$ 個質因數 $3$，所以 $3^{r+1}\nmid\overbrace{1\dots\dots\dots1}^{3^r}$
於是
證明其他情況
$n$ 為偶數或 $5$ 的倍數，顯見不成立。
先考慮 $\gcd(n,9) = 1$ 的 $n$，透過 歐拉定理 知道 $10^{\varphi(n)}\equiv1\pmod{n}$ 且 $10^{\varphi(n)}\equiv1\pmod{9}$
因此 $n\mid\overbrace{1\dots\dots\dots1}^{\varphi(n)}$，換句話說 $\mathcal{L}(n)\leq\varphi(n)< n$ 所以這類的 $n$ 不成立。
接著對於 $\gcd(n,9) = 3$ 的 $n$，令 $m=\frac{n}{3}$。則 $\gcd(m,9)=1$ 那麼
最後 $\gcd(n,9) = 9$ 的 $n$，令 $m=\frac{n}{9}$。則 $\gcd(m,9)=1$ 那麼
於是證明全部完成。 $\blacksquare$
觀察
我一開始是用程式檢查，然後觀察到一些有趣的性質(可能)： 🤔
- 如果 $n=p^k$，其中 $p$ 為非 $2, 5$ 的質數。則 $\mathcal{L}(n)=\mathcal{L}(p)\times p^{k-1}$。
- 如果 $n=\prod\limits_{i=1}^{m}p_i^{k_i}$，其中 $p_i$ 為非 $2, 5$ 的質數。則
如果上面的性質都正確，那麼原題瞬間秒解。
- $\mathcal{L}(3^k)=\mathcal{L}(3)\times 3^{k-1} = 3^k$
- 對於其他的 $n$ 則是 $$ \mathcal{L}(n)\leq\prod_i\mathcal{L}(p_i)\times p_i^{k_i-1}< \prod_i p_i^{k_i}=n $$
後記
對於 $\gcd(9,p)=1$ 存在 $a,b\in\mathbb{Z}$ 使得 $a,b$ 滿足 $9a+np=-1$。
然後證明對於所有的 $k$ 都不會滿足以下式子。
$$ \overbrace{1\dots1}^{k}\neq a \pmod{p} $$