創作整数問題#51解法&創作整数問題#52

2次試験に向けてスパートが掛かる時期となりました。インフルエンザが猛威を奮っていますが、受験生の皆さんは体調管理に十分気を付けて頑張って下さい!

前回は「メルセンヌ数」に関する問題でした。今回はまた方程式に戻ってみます。


創作整数問題#52


《問題#52》

方程式 $a^2 b=a^3+3b^5$ を満たす整数の組$(a,\,b)$は無数に存在することを示せ。

(創作問題)


前々回の問題#50は$$a^2 b=a^3+2b^2$$という方程式の整数解を求める問題でした。これに対して本問は少し毛色が違い、問題#50より難しくなっています。

解が無数に存在することは無数の解を構成する方法を見つけさえすれば証明できます。問題はどうやってそれを見つけるかですが・・・?

 

 

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


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


$2^{n}-1$ と $2^{2019}-1$ が互いに素となるような$2019$未満の自然数$n$はいくつ存在するか。


タネに気が付けばあっさり解けます。

●   ●   ●

解答例以下、$M_n=2^n-1$ と表し、整数$x$、$y$の最大公約数を$\text{GCD}(x,y)$と表すことにする。

 

自然数$m$、$n$について$d=\text{GCD}(m,n)$ とするとき、$$\text{GCD}(M_m,M_n)=M_d$$が成立することを示す(ただし$m \leqq n$)。

 

《証明》

まず$$\text{GCD}(M_n,M_m) = \text{GCD}(M_m,M_n-M_m)$$が成り立つ。ここで、$$\begin{align} M_n-M_m &= 2^{n}-2^{m} \\ &= 2^{m}(2^{n-m}-1) \\ &= 2^m M_{n-m} \\ &= (M_m + 1)M_{n-m} \end{align}$$と式変形できる。$M_m + 1$ は$M_m$と互いに素であるから、これより$$\text{GCD}(M_n,M_m) = \text{GCD}(M_m,M_{n-m})\ \ \ \cdots (★)$$が成り立つ。

 

除法の性質より、等式 $n=q_{1}m+r_{1}$ を満たすような整数$q_{1}$、$r_{1}$($0 \leqq r_{1} < m$)が存在し、性質$(★)$を繰り返し用いることにより、関係式$$\text{GCD}(M_n,M_m) = \text{GCD}(M_m,M_{r_{1}})$$を得る。このとき $M_m>M_{r_{1}}$ であり、$m$を$r_1$で割ったときの余りを$r_2$とすれば、同様の操作により$$\text{GCD}(M_m,M_{r_{1}})=\text{GCD}(M_{r_{1}},M_{r_{2}})$$を得る。これを繰り返していくと、ある余り$r_{j+1}$について $r_{j+1}=0$ となり、$$\text{GCD}(M_n,M_m)=\text{GCD}(M_{r_{j}},0)$$となる。ここで$$\text{GCD}(n,m)=r_{j}$$であるが、仮定より$$d=r_{j}$$である。したがって$$\text{GCD}(M_n,M_m)=\text{GCD}(M_{d},0)=M_{d}$$を得る。

(了)

 

 

これより、$M_{n}$と$M_{2019}$が互いに素となるような$2019$未満の自然数$n$は、$2019$と互いに素であるような$2019$未満の自然数$n$の個数に等しいことが言える。$2019$を素因数分解すると$$2019=3 \cdot 673$$となるから、$2019$未満の自然数から$3$の倍数と$673$の倍数を除いた個数を調べればよく、そのようなものは$$2018-672-2=1344$$だけ存在する。

 

以上より求める個数は $\color{red}{1344}$ 個となる。


(コメント)

お手頃な問題だったのではないでしょうか(笑)。余談ですが$M_{2019}$は$608$桁の数であり、素因数分解は容易ではありません。

 

「$n$が$m$で割り切れる⇔$a_n$が$a_m$で割り切れる」という性質をもつ数列$a_n$はメルセンヌ数の他に、フィボナッチ数列やレピュニット数列などが知られています(多分他にも沢山あると思います)。どのような数列がこの性質を持つのでしょうか?

 

メルセンヌ数列$M_{n}$の漸化式は$$M_{n+1}=2M_{n}+1$$で、フィボナッチ数列$F_{n}$の漸化式は$$F_{n+2}=F_{n+1}+F_{n}$$で、レピュニット数列$R_{n}$の漸化式は$$R_{n+1}=10R_{n}+1$$でそれぞれ与えられますが、何かヒントが隠されているでしょうか?

 

また、解答例の中で示した補題から、$M_n$がメルセンヌ素数ならば$n$が素数であることが示されます。現在発見されているメルセンヌ素数は51個ですが、メルセンヌ素数が無限に存在するか否かについてや、どのような$n$に対して$M_n$がメルセンヌ素数となるかについてはほとんど何も分かっていません。

 

メルセンヌ数は奥が深いですね!


 

 

コメントを残す

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