創作整数問題#48解法＆創作整数問題#49

平成最後の大晦日を迎えますが、毎年恒例の渋谷駅前のカウントダウンは一段と盛り上がりそうです。ハロウィンでの騒動の件もありましたので、今回はいつも以上に穏やかに行われて欲しいものですね･･･。

---

創作整数問題#49

---

《問題#49》

${\displaystyle \sum _{k=1}^n{\displaystyle \frac{1}{k}}}$ は$2$以上の任意の整数$n$に対して整数にならないことを示せ。

（創作問題）

---

創作問題としてはいますが、かなり有名な問題だと思います。

 

 

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

---

創作整数問題#48（解き方）

---

---

「下２桁」というのが意外に曲者だったのではないでしょうか。題意を数式で表現すると、$$\begin{array}{}\text{･･･ (A)}& 5^n\equiv 1(\mathrm{mod}{48}^2)\end{array}$$を満たすような最小の自然数$n$を求めよ、ということになります。$10$進法の場合だと下2桁が$01$となるのは$$5^n\equiv 1(\mathrm{mod}{10}^2)$$となるときなので、$10$を$48$に変えれば$48$進法の場合になります。

さて、ある$n$について$5^n$を${48}^2(=2^8\cdot 3^2)$で割ったときの余りが$1$になるには、まず$5^n$を$3^2$、即ち$9$で割ったときの余りが$1$となる必要があります（必要条件による絞り込み）。

●　　　●　　　●

（１）$mod{3}^2$ を考える

$$5^n\equiv 1(\mathrm{mod}3)$$となるのは$n$が偶数のときです。これは $5^2=25\equiv 1(\mathrm{mod}3)$ であることから分かります。次に$mod9$ を考えますが、$n$が偶数のときのみを考えればよく、$5^2=25\equiv -2(\mathrm{mod}9)$ より、$$5^6\equiv (-2{)}^3=-8\equiv 1(\mathrm{mod}9)$$がすぐに分かりますので、$$\begin{array}{}\text{･･･ (B)}& 5^n\equiv 1(\mathrm{mod}9)\end{array}$$を満たすような自然数$n$は$6$の倍数であることが分かりました。

●　　　●　　　●

（２）$mod{2}^8$ を考える

次に$mod256$ を考えますが、（１）の考察より$n$が$6$の倍数のときのみを考えればよく、$5^6=15625\equiv 9(\mathrm{mod}256)$ であることはすぐ計算できます。ただ、このまま$mod256$ で始めても良いのですが、$256$というのは法としてはやや大きい数なので上手く絞り込まなければ解の候補の数が膨れ上がってしまいます。

そこでまず$mod16$ で考えてみます。すると$$5^4=625\equiv 1(\mathrm{mod}16)$$がすぐに分かりますので、自然数$n$は少なくとも$4$の倍数でなければなりません。もう少し絞り込んでみましょう。

次に$mod32$ を考えますが、先ほどの計算から、$n$は$4$の倍数でなければならないので、少し計算して $5^8\equiv 1(\mathrm{mod}32)$ を得ます（このとき $5^4\equiv 17(\mathrm{mod}32)$ となって$1$にならないことを確認しています）。

全く同様にして $5^{16}\equiv 1(\mathrm{mod}64)$ を得ます（このとき $5^8\equiv 33(\mathrm{mod}64)$ となって$1$にならないことを確認しています）。

･･･そろそろ計算も面倒になって来るので、次の補題を示しておきましょう。

●　　　●　　　●

《補題》

$0$以上の整数$k$に対して$$5^{2^k}\equiv 2^{k+2}+1(\mathrm{mod}{2}^{k+3})$$が成り立つ

（証明）

$k=0$ のとき、$5\equiv 2^2+1(\mathrm{mod}{2}^3)$ となり成り立っている。

$l$をある自然数とし、$k=l$ のとき、関係式$$5^{2^l}\equiv 2^{l+2}+1(\mathrm{mod}{2}^{l+3})$$が成り立っていると仮定すると、$N$をある整数として$$\begin{array}{rl}{5}^{2^{l+1}}& =5^{2\cdot 2^l}\\ & ={\left(5^{2^l}\right)}^2\\ & =(2^{l+3}\cdot N+2^{l+2}+1{)}^2\\ & =2^{2(l+3)}\cdot N^2+2^{2(l+2)}+\text{color}red1\\ & +2^{2(l+3)}\cdot N+\text{color}red{2}^{l+3}+2^{l+4}\cdot N\\ & \equiv \text{color}red{2}^{l+3}+1(\mathrm{mod}{2}^{l+4})\end{array}$$と計算できる。これより $k=l+1$ のときも成り立つから、$0$以上の任意の整数$k$に対して$$5^{2^k}\equiv 2^{k+2}+1(\mathrm{mod}{2}^{k+3})$$が成り立つことが示された。

□

●　　　●　　　●

この補題を利用することで、

$5^{16}\equiv 65(\mathrm{mod}128)$、$5^{32}\equiv 1(\mathrm{mod}128)$、

$5^{32}\equiv 129(\mathrm{mod}256)$、$5^{64}\equiv 1(\mathrm{mod}256)$

がそれぞれ簡単に得られます。

したがって、$$\begin{array}{}\text{･･･ (C)}& 5^n\equiv 1(\mathrm{mod}256)\end{array}$$を満たすような自然数$n$は$64$の倍数であることが分かりました。

●　　　●　　　●

以上（１）と（２）の考察より、方程式$(\text{A})$を満たすような自然数$n$について、$6$の倍数かつ$64$の倍数、即ち$192$の倍数であることが必要十分なので、最小の自然数$n$は$$n=\text{color}red192$$と求めることができます。

---

（コメント）

$48$進法ということで少し身構えてしまうかもしれませんが、要はmodの計算だけですね。

また、補題ということでわざわざ$$5^{2^k}\equiv 2^{k+2}+1(\mathrm{mod}{2}^{k+3})$$という関係式を示しましたが、これは、

$5^2\equiv 1(\mathrm{mod}{2}^3)$ → $n$は$2$の倍数
$5^4\equiv 1(\mathrm{mod}{2}^4)$ → $n$は$4$の倍数
$5^8\equiv 1(\mathrm{mod}{2}^5)$ → $n$は$8$の倍数
$5^{16}\equiv 1(\mathrm{mod}{2}^6)$ → $n$は$16$の倍数
$⋮$

という仕組みになっているためです。もちろん$$5^{2^k}\equiv 1(\mathrm{mod}{2}^{k+2})$$という関係式も帰納法で簡単に証明できますし、補題なんぞ示さずにひたすら計算してゴリ押すこともできます。

また、冪の合同式について次の定理が知られています。

●　　　●　　　●

《定理》

$$a\equiv b(\mathrm{mod}n)⟹a^n\equiv b^n(\mathrm{mod}{n}^2)$$

（証明）

$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\cdots +b^{n-1})$$より、$a\equiv b(\mathrm{mod}n)$のとき、1つ目の括弧内は$n$で割り切れる。また、2つ目の括弧内には$n$個の項が存在しており、$a\equiv b(\mathrm{mod}n)$であるから、$$\begin{array}{rl}& a^{n-1}+a^{n-2}b+\cdots +b^{n-1}\\ & \equiv a^{n-1}+a^{n-1}+\cdots +a^{n-1}\\ & =n{a}^{n-1}\\ & \equiv 0(\mathrm{mod}n)\end{array}$$となる。故に2つ目の括弧内も$n$で割り切れるから、$a^n-b^n$ は$n^2$で割り切れる。

□

●　　　●　　　●

これより、実は $5^4\equiv 1(\mathrm{mod}48)$ が分かった時点で$$5^{4\cdot 48}=5^{192}\equiv 1(\mathrm{mod}{48}^2)$$が分かってしまいます（上記の定理で $(a,b,n)=(5,1,48)$ とした場合に相当します）。

ところがこの定理は必要性しか保証しないので、十分性、つまり$$5^n\equiv 1(\mathrm{mod}{48}^2)$$を満たす$n$が$192$（の倍数）しか存在しない、ということまでは保証していません。

本問のケースでは偶然にも最小解が得られましたが、例えば$$5^n\equiv 1(\mathrm{mod}\text{color}red{42}^2)$$を満たす$n$を求める際には利用できません。実際、$$5^n\equiv 1(\mathrm{mod}42)$$を満たす最小の$n$は$6$なので、$42$倍すると$252$となりますが、$$5^n\equiv 1(\mathrm{mod}{42}^2)$$を満たす最小の$n$は、その$7$倍の$42$であることが確かめられます。

---

なお、解答例で証明した補題は管理人が問題を解いているときに見つけたものなので、広く知られているものではないと思います･･･。良い別解もありそうな気がします。