自然数nと自然数n+1は互いに素であることを証明せよ

  • このエントリーをはてなブックマークに追加
  • Pocket
  • LINEで送る

整数に関する問題は、パズルのようで面白い。しかし、解き方が分からないとお手上げという問題も多いのが困りどころだ。

整数は今後、大学入試で頻繁に取り上げられる分野になるので、得点源にするためには多くの問題を解いて、解法のパターンを頭に入れておくと良いだろう。

では試しに、1問解いてみよう。割と素直な問題で、背理法を使う。

問題文

自然数nと自然数n+1は互いに素であることを証明せよ。

実にシンプルな問題文だ。自然数とは、正の整数の事を指すものとしよう。

互いに素とは最大公約数が1であることだ。

証明

背理法によるアプローチが簡単だろう。

自然数nと自然数n+1が互いに素でないと仮定する。その場合、最大公約数gが存在することになる。

ここでgとは、g≠1を満たす自然数のことだ。(互いに素でないため)

すると自然数nとn+1はそれぞれ、ある自然数a,bが存在して

n=a×g

n+1=b×g

と表すことができる。ここでn<n+1であることから明らかに、a<bである。

さて、b×g=n+1=a×gであるので

(b-a)×g=1

つまり、g=1/(b-a)

ここで、左辺が自然数であることから右辺も自然数でなければならないが、1/(b-a)が自然数である為にはb-a=1でなければならない。

しかし、g=1/(b-a)=1であるならば、これはg≠1と矛盾する。

故に、nとn+1が互いに素でないと仮定したことが誤りである。

背理法より、任意の自然数nについてnとn+1は互いに素である。

以上。

  • このエントリーをはてなブックマークに追加
  • Pocket
  • LINEで送る

節約の基本はハピタス活用から始めるのが簡単

書籍の購入、資料の請求、契約の見直し、クレジットカードの発行などは店頭よりもインターネットを経由した方が特典が豊富です。

インターネットを利用して買い物をするなら、ハピタスを経由するようにすると、各企業が提供しているポイントや特典の他にもハピタスからのポイントバックを受けることができます。私がハピタスを愛用している理由として

  • 登録無料

  • 交換レートが1ポイント=1円のレートで300ポイントから交換可能

  • 換金の手数料が無料

  • ウェブサイトが非常にシンプル


新規登録された方に100ポイントのプレゼントしています。

ハピタス

SNSでもご購読できます。

コメントを残す

*

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください