創作整数問題#73解法&創作整数問題#74

今日は11月11日、レピュニットの日ですね! という訳でレピュニットっぽい問題を用意しました!


創作整数問題#74


《問題#74》

任意の自然数$n$に対して、$3$乗すると下$n$桁の数字がすべて$1$になるような$n$桁以下の正の整数が存在することを示せ。

(創作問題)


手の付け所が解らない問題に遭遇した際は、まず何らかの規則性を見つけられないか試行錯誤してみましょう。規則性を見つけた後に方針を立てます。

 

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


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


整数 $a_n=8^{n+2}+9^{2n+1}$($n=1,\,2,\,3,\cdots$)のすべてを割り切る素数を求めよ。


「すべてを割り切る」ということは$a_1$も割り切るということを意味します。そこでまずは$a_1$を割り切る素数に着目しましょう。「必要条件から攻める」というのは全称命題の基本的な攻略法です。

解答例

 

求める素数を$p$と置く。$a_1=1241$ より、$p$は$1241$の素因数として現れる。$1241<36^2=1296$ となるので、$35$以下の素数で$1241$を割り切るものを探していくと$17$が見つかり、$$1241=17 \cdot 73$$と素因数分解できることが分かる。したがって、素数$p$の値としてあり得るものは $17$ または $73$ である。

 

ここで $a_2=63145$ である。これは$73$で割り切れるが、$17$では割り切れない。よって $p=73$ の場合に限られる。

 

以下、任意の正の整数$n$に対して$a_{n}$が$73$で割り切れることを示す。

 

 ①数学的帰納法による証明

$n=1$ のとき $a_1=17 \cdot 73$ より、$a_n$は$73$で割り切れる。

 

$n=i$($i=2,3,4,\cdots$)のとき$a_i$が$73$で割り切れると仮定する。$a_{i+1}$の式を変形すると$$\begin{aligned} & \quad \, \, 8^{(i+1)+2}+9^{2(i+1)+1} \\ &=8 \cdot 8^{i+2}+81(9^{2i+1}) \\ &= 8 \cdot 8^{i+2}+81(a_i-8^{i+2}) \\ & \quad \quad \quad (\because a_i=8^{i+2}+9^{2i+1}) \\ &= 81a_i-73 \cdot 8^{i+2} \end{aligned}$$となる。仮定より、$a_i$は$73$で割り切れるから、$$a_{i+1}=8^{(i+1)+2}+9^{2(i+1)+1}$$も$73$で割り切れる。故に $n=i+1$ でも成立する。

 

以上より、数学的帰納法から任意の正の整数$n$に対して$a_{n}$が$73$で割り切れることが示された。したがって、求める素数$p$は$$\color{red}{73}$$である。

 

②合同式による証明

$$\begin{aligned} a_n &= 8^{n+2}+9^{2n+1} \\ &=64 \cdot 8^n+9 \cdot 81^n \\ &\equiv (-9) \cdot 8^n+9 \cdot 8^n \pmod{73} \\ &= 0 \end{aligned}$$より、$a_n$は$n$の値によらず$$a_n \equiv 0 \pmod{73}$$を満たすから、任意の正の整数$n$に対して$a_{n}$が$73$で割り切れることが示された。したがって、求める素数$p$は$$\color{red}{73}$$である。


 

整除性を扱う整数問題にはこういった指数型数列の問題が頻繫に登場しますが、本問もそのよくあるうちの一つです。冒頭でも少し触れましたが、「すべての~に対して・・・が成り立つ」というタイプの命題は「全称命題」と呼ばれます。

特に数列や関数が絡んだ全称系の問題では $n=1$ や $x=0$ などの特殊な場合を考えて、初めに必要条件を求めてしまうのが定石です。必要条件で候補を何個かに(あるいは特定の範囲内に)絞ってから、その有限な幾つかについて十分性を確認するという解き方は整数問題の基本的な解法でもあります。よく理解しておきましょう。

“創作整数問題#73解法&創作整数問題#74” への2件の返信

  1. 1241の素因数分解はやや面倒なので,私は以下のように考えていました.

    定番の手法で,a[n+2]=89a[n+1]-648a[n]が得られ,
    これは,a[0]=8^2+9とおけば,n=0でも成り立つことがわかる.

    648の素因数である2,3が条件を満たさないことは明らかで,
    それ以外の素数pで
    「a[n],a[n+1]がともに割り切れる」⇔「a[n+1],a[n+2]がともに割り切れる」
    (n=0,1,2,…)から,
    題意を満たす素数は,a[0]の素因数である73が唯一の候補であり,
    a[1]が73で割り切れることを確認すれば終了.
    実際,1241/73=17.

    1. たけちゃん さん

      コメントありがとうございます。お久し振りですね。

      $a_0=73$ がそのまま答えになってしまうので問題文では $n=1,\,2,\,3,\cdots$ と書いていましたが、あっさり見破られてしまいましたね(笑)
      仰る通り、漸化式を組み立ててしまえばあっと言う間に解決してしまう問題でした。
      別解のご提供に感謝致します。

コメントを残す

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