創作整数問題#71解法&創作整数問題#72

今年はオリンピックも無かったのに、結局10月は一日も休日が無いのでしょうか・・・。


創作整数問題#72


《問題#72》

$3$乗すると下$4$桁の数字が$7272$になるような正の整数のうち、最小のものを求めよ。

(創作問題)


まずは$3$乗すると下$2$桁の数字が$72$になるような正の整数を探しましょう。その後は場合分けしつつ、文字で置いて計算していきます。

 

 

» 答えはこちら

答えは $738$ です。

» 閉じる


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


$1$を$70$個並べてできる数 $N=\underbrace{111 \cdots 111}_{70\text{個}}$ は$71$で割り切れることを示せ。

前回のヒントの中でフェルマーの小定理の利用について触れました。フェルマーの小定理により、素数$p$と任意の自然数$n$に対して $n^{p}-n$ が常に$p$の倍数となることが言えます。これにおいて $n=10$、$p=71$ とすれば後は一直線です。

ここではフェルマーの小定理を既知として扱います。

解答例

 

$N=\underbrace{111 \cdots 111}_{70\text{個}}$ より、$$N=\dfrac{10^{70}-1}{9}$$と表せる。ここで$10$と$71$は互いに素であるから、$N$に$10$を乗じた$$10N=\dfrac{10^{71}-10}{9}$$が$71$で割り切れることを示せばよい。

 

フェルマーの小定理より、素数$p$と任意の自然数$n$に対して $n^{p}-n$ が常に$p$の倍数となることが言える。$71$が素数であることに着目して $n=10$、$p=71$ とすると、$10^{71}-10$ は$71$で割り切れることが言える。これより$10N$は$71$で割り切れるから、$N$は$71$で割り切れる。


(コメント)

本問が良問かどうかはさておき、フェルマーの小定理を使えば割り算をせずに倍数判定が可能です。フェルマーの小定理を題材にした入試問題は割とよく出題されています。

 

因みに、フェルマーの小定理は以下のような流れで証明できます。

 

$p$ を任意の素数、$n$ を $p$ で割り切れない任意の整数とするとき、2つの集合 $\{n, 2n, 3n, \cdots , (p-1)n\}$ と $\{1, 2, 3, \cdots , p-1\}$ は $\text{mod}\, p$ において、並び替えを除いて等しくなることが言えます。これより、$$(p-1)! \cdot n^{p-1} \equiv (p-1)!$$となるので、$$n^{p-1} \equiv 1$$が従います。

 

或いは、あまりやりたくないですが無理やり割り算を実行して商が

15649452269170579029733959311424100156494522691705790297339593114241

になることを示しても解答としては一応成立します。


“創作整数問題#71解法&創作整数問題#72” への1件の返信

コメントを残す

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