創作整数問題#83解法&創作整数問題#84

創作整数問題シリーズは4週間振りの更新です。


「ディオファントスの墓碑銘」と呼ばれる、古代ギリシャの数学者ディオファントスの墓石に刻まれた有名な問題があります。

ディオファントスの人生は、6分の1が少年期、12分の1が青年期であり、その後に人生の7分の1が経って結婚し、結婚して5年で子供に恵まれた。ところがその子はディオファントスの一生の半分しか生きずに世を去った。自分の子を失って4年後にディオファントスも亡くなった。

さて、ディオファントスは何歳まで生きたでしょう?という問題です。小中学生にちょうど良いレベルの問題かもしれません。


創作整数問題#84


《問題#84》

$0$から$9$までのすべての数字は自然数の平方根の小数点以下第$3$位の数字として現れることを示せ。

(創作問題)


出来不出来の分かれそうな問題です。ちょっとした腕試しにどうぞ。

 

証明問題につき、解答例は次回掲載します。


創作整数問題#83(解き方)


循環小数を表示したときに繰り返される数字の列を循環節という。例えば、$$\dfrac{1}{7}=0.\underline{142857}14285714\ldots$$であるから$\dfrac{1}{7}$の循環節は下線部の$\underline{142857}$であり、循環節の長さは$6$である。

(1)$2$と$5$を除く素数$p$について、$\dfrac{1}{p}$の循環節の長さは $p-1$ の約数になることを示せ。

(2)$\dfrac{1}{83}$の循環節の長さを求めよ。

(3)十進法表記において、最高位の数字が$8$、下$1$桁の数字が$3$で、間がすべて$0$であるような$3$桁以上の整数 $800 \ldots 003$ のうち、$83$で割り切れるものを1つ求めよ。


(1)の証明が難しいですが、証明さえできれば易しい(?)問題です。ここではフェルマーの小定理が成立することを既知とします。

解答例

 

(1)

$10$と素数$p$は互いに素であるからフェルマーの小定理より$$10^{p-1}-1 \equiv 0 \pmod{p} \quad \cdots ①$$が成り立つ。また、$\dfrac{1}{p}$の循環節の長さを$\ell$とすると、循環節の定義より$$10^{\ell}-1 \equiv 0 \pmod{p} \quad \cdots ②$$が成り立つ。

 

ここで $\ell$ が $p-1$ の約数でないと仮定する。このとき $q \geqq 0$、$0 < r < \ell$ を満たす整数$q$、$r$が存在して $p-1=q\ell+r$ と置けるから、$$\small \begin{aligned}
& \quad \ 10^{p-1}-1 \\
&=10^{q \ell+r}-1 \\
&=10^{q \ell} \cdot 10^{r}-10^{r}+10^{r}-1 \\
&=\left(10^{q \ell}-1\right) 10^{r}+10^{r}-1 \\
&=\left\{(10^{\ell})^{q}-1\right\} 10^{r}+10^{r}-1 \\
&=(10^{\ell}-1)\left\{(10^{\ell})^{q-1}+(10^{\ell})^{q-2}+\cdots+1\right\} 10^{r}+10^{r}-1
\end{aligned}$$と式変形できるが、これと$①$、$②$より$$10^{r}-1 \equiv 0 \pmod{p}$$が導かれる。これより$r$は$\dfrac{1}{p}$の循環節の長さとなるが、$r<\ell$ であるからこれは$\ell$の最小性に反し不合理である。

 

よって背理法より、$\ell$ は $p-1$ の約数であることが示された。

 

 

(2)

(1)より、$\dfrac{1}{83}$の循環節の長さとなり得るのは$82$の約数、つまり$1$、$2$、$41$、$82$のいずれかに限られる。

$$\begin{aligned}
10^{1} & \equiv 10 \pmod{83} \\
10^{2} & \equiv 17 \pmod{83}_{ } \\
10^{4} & \equiv 17^{2} \equiv 40 \pmod{83} \\
10^{8} & \equiv 40^{2} \equiv 23 \pmod{83} \\
10^{16} & \equiv 23^{2} \equiv 31 \pmod{83} \\
10^{32} & \equiv 31^{2} \equiv 48 \pmod{83} \\
10^{41} &=10^{32} \cdot 10^{8} \cdot 10^{1} \\
& \equiv 48 \cdot 23 \cdot 10 \equiv 1 \pmod{83}
\end{aligned}$$

となるから、$\dfrac{1}{83}$の循環節の長さは $\color{red}{41}$ と求められる。

 

 

(3)

(2)より $10^{41}=83N+1$ を満たすような整数$N$が存在する。この両辺に$80$を乗じて$$80 \cdot 10^{41}=83 \cdot 80 \cdot N+80$$さらに両辺に$3$を加えると$$\therefore 8 \cdot 10^{42}+3=83 \cdot 80 \cdot N+83$$となる。この右辺は$83$の倍数であるから、求める整数の一つは$$\color{red}{8\underbrace{00 \ldots 00}_{41\text{個}}3}$$である。

 


 

本問のテーマは見ての通り「循環節」です。(1)で証明した事柄は素数の逆数の循環節に関する有名な事実なので、知らなかったという人はこれを機に覚えておくと良いでしょう。(3)が本問の主眼なのですが、素数の逆数という小さな数が巨大な整数の求値に応用できるというのはちょっと意外に思われるかもしれません。本当は(3)単体で出題しようかとも思ったのですが、単なる腕力勝負の計算問題にするのも何となく勿体無いと思い、誘導設問を付けてみました。

なお、こういう問題では(1)ができていなくても「(1)の結果」を利用して(2)と(3)だけ先に解いてしまうことができます。得点に貪欲に喰らい付く精神は大切です。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です