倍数の問題                               戻る

 自然数 n を含む数の倍数問題は、毎年どこかの大学で出題される頻出問題である。

たとえば、 n が自然数であるとき、

      n4+2n3+11n2+10n は24の倍数であることを証明せよ。


というタイプの問題である。

 このような問題の特徴は、それまで学んだことを生かして、各個人の独創的なアイデアが
求められるという点であろう。それ故に、受験生泣かせでもある。

 ただ、基本的な解法は広く知れ渡り、特に、いくつかの具体例から法則性を学び、それを
数学的帰納法で示すという流れが多いので、安心してよいと思う。

 十分高校数学的で数学的な論述を見る問題として適切であり、また受験生個々の数学力
が如実に表れるので、それが入試問題として好まれる理由だろう。

 上述の問題を解いてみよう。ボーッと眺めていても問題は解けない。次のような式変形が
ポイントだろう。これは、高校で学ぶ「連続する2整数の積は偶数」ということを意識している。

(解)  n4+2n3+11n2+10n=n(n3+2n2+11n+10)

                 =n(n+1)(n2+n+10)

                 =n(n+1){(n+2)(n−1)+12}

                 =(n−1)n(n+1)(n+2)+12n(n+1)

  n(n+1)は連続する2整数の積で、2の倍数より、12n(n+1)は24の倍数である。

  (n−1)n(n+1)(n+2)=4!・n+24=24・n+24 より、24の倍数である。

 よって、n4+2n3+11n2+10n は、24の倍数である。  (終)

 数学的帰納法による証明も考えられるが、式変形や用いられる理論は上記とほとんど同
様である。

 いくつか別な例題を見ていこう。
      (これらの問題は当HPがいつもお世話になっているS(H)さんよりご紹介いただきました。

名古屋市大(1982年)

n を自然数とするとき、 3n+1+42n-1 は13で割り切れることを証明せよ。

(解) n=1 のとき、 3n+1+42n-1=9+4=13 は明らかに13で割り切れる。

   n=k(k≧1)のとき、成り立つと仮定する。

     すなわち、3k+1+42k-1 は13で割り切れる。

   このとき、 3k+1+42k-1 =13m (mは自然数) とおける。

   n=k+1 のとき、 3k+2+42k+1=3・3k+1+16・42k-1

                       =3・(13m−42k-1)+16・42k-1

                       =13(3m+42k-1) より、13で割り切れる。

    よって、n=k+1 のときも成り立つ。

  したがって、すべての自然数 n に対して、 3n+1+42n-1 は13で割り切れる。  (終)


 平成21年3月21日付けで、HN「zk43」さんから、数学的帰納法に依らない証明をいた
だいた。

(別解) F(n)=3n+1+42n-1 とおくと、

    F(n+3)=3n+4+42n+5=27・3n+1+642・42n-1

   ここで、 27≡1 (mod 13) 、 642≡(−1)2=1 (mod 13) より、

     F(n+3)≡F(n) (mod 13)

   よって、題意を満たすためには、F(1)、F(2)、F(3) について調べれば十分である。

   F(1)=9+4=13≡0 (mod 13) 、 F(2)=27+64=91≡0 (mod 13)

   F(3)=81+1024=1105≡0 (mod 13)

  以上から、すべての自然数 n に対して、 3n+1+42n-1 は13で割り切れる。  (終)


 また、zk43さんは、剰余について新しい視座を見出された。

 すなわち、 3 : 3 、9 、27 、81 、243 、729 、・・・ において、13を法とすれば、

       3 : 3 、9 、1 、3 、9 、1 、・・・

と、「3 、9 、1」が循環する。同様に、

 4 : 4 、16 、64 、256 、1024 、4096 、16384 、・・・ において、

13を法とすれば、

       4 : 4 、3 、12 、9 、10 、1 、4 、・・・

と、「4 、13 、12 、9 、10 、1」が循環する。このとき、

・・・
n+1 10 ・・・
n+1を13で割った余り ・・・
2n−1 11 13 15 17 ・・・
2n-1を13で割った余り 12 10 12 10 12 10 ・・・
F(n)を13で割った余り ・・・

なので、すべての自然数 n に対して、 3n+1+42n-1 が13で割り切れることは十分予想
できる。

(コメント) 今まで経験のない視座に感動しました!zk43さんに感謝します。

東京工業大(1986年)

 整数 a=19+(−1)n-14n-3 (n=1、2、3、・・・)のすべてを割り切る素数を
求めよ。


(解) n=1 のとき、 a1=19+(−1)n-14n-3=19+2=21=3・7

   n=2 のとき、 a2=19+(−1)n-14n-3=361−32=329=7・47

 よって、 a のすべてを割り切る素数は、7であることが類推できる。

 この類推が正しいことを、数学的帰納法により示す。

n=1 のとき、a1=19+(−1)n-14n-3=19+2=21 は明らかに7の倍数である。

n=k(k≧1)のとき成り立つと仮定する。即ち、a=19+(−1)k-14k-3 は7の倍数。

   このとき、 19+(−1)k-14k-3=7m (mは自然数) とおける。

 n=k+1 のとき、 ak+1=19k+1+(−1)4k+1

                 =19・19−16・(−1)k-14k-3

                 =19・(7m−(−1)k-14k-3)−16・(−1)k-14k-3

                 =7(19m−5(−1)k-14k-3) より、7の倍数。

 よって、n=k+1 のときも成り立つ。

したがって、すべての正の整数 n に対して、

      19+(−1)n-14n-3 は7の倍数である。

 すなわち、 19+(−1)n-14n-3 のすべてを割り切る素数は、7である。  (終)

(コメント) 一度、数学的帰納法の証明に慣れてしまうと、両者は全く機械的に行うことが
      でき、あまり面白さは感じられない。

 直接的に、例えば、 3n+1+42n-1=13F(n) となるF(n)を見いだすことは可能だろう
か?S(H)さんは、こちらの方法に関心を持たれているようだ。

 S(H)さんによれば、

     F(n)=(1/52)(36・3n-1+16・16n-1

と書けるらしい。

 平成21年3月22日付けで、zk43さんが、(2)について合同式を利用する解法を示され
たので紹介したい。

(別解) n=1 のとき、 a1=19+(−1)n-14n-3=19+2=21=3・7

   n=2 のとき、 a2=19+(−1)n-14n-3=361−32=329=7・47

   よって、 a のすべてを割り切る素数は、7であることが類推できる。

   このとき、すべての正の整数 n に対して、7を法として考えると、

     a=19+(−1)n-14n-3 において、

    19≡(−2) (mod 7)

    (−1)n-14n-3=(−1)n-14n-4・2

              =(−1)n-116n-1・2

              ≡(−1)n-1n-1・2 (mod 7)

              ≡−(−2) (mod 7)

     よって、 a≡(−2)−(−2)=0 (mod 7)  (終)

 また、zk43さんは、「n が奇数のとき、 a≡0 (mod 3)」であることも示された。

 すなわち、n が奇数のとき、 a=19+(−1)n-14n-3≡1+(−1)=0 (mod 3)


 次の 静岡大学 前期 理系(2009) の(1)は、確実に、名古屋市大(1982)の問
題に類似している。さらに、(2)は、京都大学 理系(2003) の問題を意識しているように
感じる。

次の問いに答えよ。

(1) すべての自然数 n に対して、4n+1+52n-1 は21で割り切れることを証明せよ。

(2) 次の条件を満たす定数でない多項式 F(x) を推定し、その推定が正しいことを
  証明せよ。

  (a) F(4)=21

  (b) すべての自然数 n に対して、xn+1+(x+1)2n-1 は F(x) で割り切れる。


(解)(1) n=1 のとき、 4n+1+52n-1=16+5=21 は21で割り切れる。

   n=k(k≧1)のとき、成り立つと仮定する。

     すなわち、4k+1+52k-1 は21で割り切れる。

   このとき、 4k+1+52k-1 =21m (mは自然数) とおける。

   n=k+1 のとき、 4k+2+52k+1=4・4k+1+25・52k-1

                       =4・(21m−52k-1)+25・52k-1

                       =21(4m+52k-1) より、21で割り切れる。

    よって、n=k+1 のときも成り立つ。

  したがって、すべての自然数 n に対して、 4n+1+52n-1 は21で割り切れる。

(2) G(x)=xn+1+(x+1)2n-1 とおくと、

      G1(x)=x2+x+1 で、G1(4)=21 より、 F(x)=x2+x+1

  と推定する。この推定が正しいことを、数学的帰納法により示す。

  n=1 のとき、明らかに成り立つ。

  n=k(k≧1)のとき、成り立つと仮定する。

     すなわち、F(4)=21 で、 G(x) はF(x)で割り切れるので、

       G(x) =F(x)Q(x) (Q(x)は多項式)

  このとき、 Gk+1(x)=xk+2+(x+1)2k+1

              =xk+2+(x+1)2(F(x)Q(x)−xk+1

              =−xk+1(x2+x+1)+(x+1)2F(x)Q(x)

              =F(x)(−xk+1+(x+1)2Q(x)) より、F(x)で割り切れる。

  よって、n=k+1 のときも成り立つ。

  したがって、すべての自然数 n に対して、xn+1+(x+1)2n-1 は F(x) で割り切れるこ

 とが示された。以上から、推定は正しく、 F(x)=x2+x+1 である。  (終)

(コメント) この問いは「数学的帰納法で」という限定条件が付いているが、直接的な証明
      も可能である。

 G(x)=xn+1+(x+1)2n-1 が、F(x)=x2+x+1 で割り切れることを、次のように計
算しても分かる。

  F(x)=x2+x+1=(x−ω)(x−ω2) なので、G(x)がF(x)で割り切れることを示す

 には、 G(ω)=0 、 G(ω2)=0 であることを示せば十分である。
                                 (→ 参考 : 「オメガ(ω)の真実」
   G(ω)=ωn+1+(ω+1)2n-1

        =ωn+1+(−ω22n-1

        =ωn+1−ω4n-2

        =ωn+1−ωn-2

        =ωn-2(ω3−1)=0

   G(ω2)=ω2n+2+(ω2+1)2n-1

         =ω2n+2+(−ω)2n-1

         =ω2n+2−ω2n-1

         =ω2n-1(ω3−1)=0

 以上から、 G(x)=xn+1+(x+1)2n-1 は、F(x)=x2+x+1 で割り切れる。

 よって、F(x)=x2+x+1 が求める多項式である。  (終)


京都大学 文系(2001年)

任意の整数 n に対し、 n9−n3 は9で割り切れることを示せ。

(解) n9−n3=n3(n6−1)=(n3−1)n3(n3+1)

   ここで、 n=3m (mは整数) のとき、 n3=27m3 なので、9で割り切れる。

  n=3m+1 (mは整数) のとき、 n3−1=27m3+27m2+9m なので、9で割り

 切れる。

  n=3m+2 (mは整数) のとき、 n3+1=27m3+54m2+36m+9 なので、9

 で割り切れる。

 以上から、任意の整数 n に対し、 n9−n3 は9で割り切れる。  (終)

(コメント) ちょっと、問題が易しすぎるような...?


 当HPがいつもお世話になっている「zk43」さんから別解を頂いた。
                         (平成21年4月13日付け)

(別解) n が3で割り切れなければ、オイラーの定理から、 n6≡1 (mod 9)

     よって、この場合、n9−n3=n3(n6−1) は、9で割り切れる。

  n が3で割り切れれば、n3 は、9で割り切れる。

     よって、この場合、n9−n3=n3(n6−1) は、9で割り切れる。

  以上から、任意の整数 n に対し、 n9−n3 は9で割り切れる。  (終)

 「zk43」さんによれば、上記の証明を鑑みて、「n8−n2 は9で割り切れる。」という問題も
作れるとのこと。

 また、「奇数の平方は、8で割ると1余るという事実を一般化して、

  奇数の2n乗は、2n+2で割ると、1余る

ということも成り立ち、結構面白いとのこと。これから、mod 2n+2 での既約剰余類群は巡
回群にはならないことが分かるそうである。zk43さんに感謝します。


 また、平成21年4月13日付けで、S(H)さんより、次のような別解をご教示いただいた。

 まず、次の定理を用いる。これは、1993年度前期の東京工業大学の入試問題である。

 (この手の問題は受験生には厳しい難問で、解答に「帰納法で示す」と書いただけで、満点の30点
  中10点が貰えたという噂が...?


定 理  n を自然数、P(x)を n 次の多項式とする。

    P(0)、P(1)、・・・、P(n)が整数ならば、

  すべての整数 k に対し、P(k)は整数である。


 わずかに n+1 個の値の様子から、すべての値の様子が分かってしまうという末恐ろし
い事実ですね!

 「整数値多項式」ということを意識すれば、次のような証明が考えられるだろう。

(証明) n 次の多項式 P(x) が、

    P(x)=a+bx+(c/2!)x(x−1)+・・・+(d/n!)x(x−1)・・・(x−n+1)

  即ち、整数値多項式 F(X)=X(X−1)(X−2)(X−3)・・・(X−k+1)/k!を用いて、

    P(x)=a+b・F1(X)+c・F2(X)+・・・+d・F(X)

 の形に書けることを数学的帰納法で示す。

 n=1 のときは、明らかに成り立つ。

 n=k(k≧1)のとき成り立つと仮定する。

 n=k+1 のとき、 P(x)は、k+1次の多項式で、その最高次の係数をAとすれば、

   P(x)−Ax(x−1)・・・(x−k) は、k次の多項式となる。

 帰納法の仮定により、

  P(x)−Ax(x−1)・・・(x−k)=a+b・F1(X)+c・F2(X)+・・・+d・F(X)

と書ける。そこで、e=A・(k+1)!とおけば、

  P(x)=a+b・F1(X)+c・F2(X)+・・・+d・F(X)+e・Fk+1(X)

と書けることが示された。よって、n=k+1のときも成り立つ。

 以上から、すべての自然数 n について、n 次の多項式 P(x) は、

    P(x)=a+b・F1(X)+c・F2(X)+・・・+d・F(X)

 の形に書ける。

 題意より、P(0)、P(1)、・・・、P(n)が整数なので、

  a 、a+b 、a+b+c 、・・・ 、a+b+c+d

はすべて整数である。このとき、a 、b 、c 、・・・ 、d はすべて整数となる。

 したがって、すべての整数 x に対して、整数値多項式 F(X)は整数値をとり、その係数

も整数なので、多項式 P(x) は、整数値をとる。

 すなわち、 すべての整数 k に対し、P(k)は整数である。  (証終)


 1993年度前期の東京工業大学の入試問題と同様の問題が、1997年度 名古屋大学の
前期理系で出題されたことを、S(H)さんよりご教示いただいた。(平成21年4月23日付け)

名古屋大学 前期理系(1997年) 

 (1) 多項式 F(x)=x3+ax2+bx+c (a、b、c は実数)を考える。
    F(−1)、F(0)、F(1) がすべて整数ならば、すべての整数 n に対し、F(n)は整数
   であることを示せ。

 (2) F(1996)、F(1997)、F(1998) がすべて整数の場合はどうか?

(解)(1) 題意より、

     F(−1)=−1+a−b+c 、F(0)=c 、F(1)=1+a+b+c はすべて整数で、

   a={ F(−1)−2F(0)+F(1) }/2 、b=−{ F(−1)+2−F(1) }/2 、c=F(0)

   このとき、すべての整数 n に対し、

    F(n)=n3+an2+bn+c

       =n3+{ F(−1)−2F(0)+F(1) }n2/2−{ F(−1)+2−F(1) }n/2+F(0)

       =n3+ F(−1)・n(n−1)/2−F(0)・(n2−1)+F(1)・n(n+1)/2

    ここで、 n(n−1)/2 、n(n+1)/2 は整数なので、

   したがって、すべての整数 n に対し、F(n)は整数となる。

(2) G(x)=F(x+1997) とおくと、 G(x)=x3+px2+qx+r (p、q、r は実数)で、

  題意より、 G(−1)、G(0)、G(1) はすべて整数。

  よって、(1)より、 すべての整数 m に対し、G(m)=F(m+1997)は整数となる。

  したがって、すべての整数 n=m+1997 に対し、

    F(n)=F(m+1997)=G(m) は整数となる。  (終)


 上記の東京工業大学の定理を用いれば、京都大学の問題は、次のように解かれる。

(別解) P(n)=(n9−n3)/9 とおく。

   このとき、 P(1)=0  、P(2)=(512−8)/9=56  、P(3)=2184 、

          P(4)=29120  、P(5)=217000  、P(6)=1119720 、

          P(7)=4483696  、P(8)=14913024  、P(9)=43046640

  さらに、 P(0)=0 なので、 P(0)、P(1)、・・・、P(9)はすべて整数となる。

  よって、定理により、すべての整数 n に対して、P(n)は整数となる。

  したがって、任意の整数 n に対し、 n9−n3 は9で割り切れる。  (別解終)

(コメント) この問題は、まさに整数値多項式の独壇場ですね!S(H)さんに感謝します。

      上記のP(n)の計算で、P(n)=(n3−1)n3(n3+1)/9 と変形してから値が整
     数になることを示す方が実戦的であろう。正直に告白すると、私は Excel さんに計
     算してもらいました...!


 上記の証明に関連して次のポリアの定理があることをS(H)さんよりご教示いただいた。

ポリアの定理  すべての整数 x に対して、多項式 P(x) が整数値をとるための

         必要十分条件は、整数 A0,A1,A2,・・・,A を適当に選び、

     P(x)=A0+A11(x)+A22(x)+・・・+A(x)

   と書けることである。ただし、

     F(x)=x(x−1)(x−2)(x−3)・・・(x−k+1)/k! とする。


(コメント) 上記の証明は、正にポリアの定理を意識した証明になっていますね!

 上記で述べられたことから、整数値多項式 F(X) の有用性が実感できたが、平成21年
4月17日付けで、S(H)さんから、基底の変換

   { 1,x,x2,x3,・・・x,・・・ } ⇔ { 1,F1(x),F2(x),・・・,F(x),・・・ }

の対応表を作ってみては...という提案があった。

 対応表があれば、上記のような手順を踏まずに直接的に多項式の別表現が得られる。

 その作り方は単純で、

   を x で割り、その商を x−1 で割り、その商を x−2 で割り、・・・・

と順次割っていけばよい。そのときの余りを用いて、新しい基底の係数が決定される。

 例えば、 x=x・1 なので、 x=1・F1(x) である。

 x2=x・x=x{(x−1)・1+1}=x・1+x(x−1)・1=1・F1(x)+2!・F2(x)

 x3=x・x2=x{(x−1)・(x+1)+1}
       =x[(x−1){(x−2)・1+3}+1]
       =x・1+x(x−1)・3+x(x−1)(x−2)・1
       =1・F1(x)+3!・F2(x)+3!・F3(x)

   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 原理は単純でも計算がだんだん辛くなりそうな...予感!

 係数を決定するだけだったら、次のように計算してもできるかな?

  x3=a・F1(x)+b・F2(x)+c・F3(x) において、

   F1(1)=1 、F2(1)=0 、F3(1)=0

   F1(2)=2 、F2(2)=1 、F3(2)=0

   F1(3)=3 、F2(3)=3 、F3(3)=1

 なので、 a=1 、 2a+b=8 、 3a+3b+c=27 より、 a=1 、b=6 、c=6

  この方法だと、行列の計算に持ち込めそうですね!

 もう少し計算してみると、

   F1(1)=1 、F2(1)=0 、F3(1)=0 、F4(1)=0 、F5(1)=0

   F1(2)=2 、F2(2)=1 、F3(2)=0 、F4(2)=0 、F5(2)=0

   F1(3)=3 、F2(3)=3 、F3(3)=1 、F4(3)=0 、F5(3)=0

   F1(4)=4 、F2(4)=6 、F3(4)=4 、F4(4)=1 、F5(4)=0

   F1(5)=5 、F2(5)=10 、F3(5)=10 、F4(5)=5 、F5(5)=1

となって、パスカルの三角形と同様な構造になっていることに気づく。

 この規則性に従って、表を作ってみた。

   
  1 2 3 4 5 6 7 8 9
10 10
15 20 15
21 35 35 21
28 56 70 56 28
36 84 126 126 84 36

 この表をもとに、x4 、x5 、x6 、x7 、x8 、x9 、・・・ を計算してみよう。

 x4=a・F1(x)+b・F2(x)+c・F3(x)+d・F4(x) とおくと、上記の表より、

 1=a
 16=2a+b  より、 b=14
 81=3a+3b+c  より、 c=81−3−42=36
 256=4a+6b+4c+d  より、 d=256−4−84−144=24

なので、 x4=1・F1(x)+14・F2(x)+36・F3(x)+24・F4(x)

 x5=a・F1(x)+b・F2(x)+c・F3(x)+d・F4(x)+e・F5(x) とおくと、上記の表より、

 1=a
 32=2a+b  より、 b=30
 243=3a+3b+c  より、 c=243−3−90=150
 1024=4a+6b+4c+d  より、 d=1024−4−180−600=240
 3125=5a+10b+10c+5d+e  より、
                          e=3125−5−300−1500−1200=120

なので、 x5=1・F1(x)+30・F2(x)+150・F3(x)+240・F4(x)+120・F5(x)

 x6=a・F1(x)+b・F2(x)+c・F3(x)+d・F4(x)+e・F5(x)+f・F6(x) とおくと、

上記の表より、

 1=a
 64=2a+b  より、 b=62
 729=3a+3b+c  より、 c=729−3−186=540
 4096=4a+6b+4c+d  より、 d=4096−4−372−2160=1560
 15625=5a+10b+10c+5d+e  より、
                        e=15625−5−620−5400−7800=1800
 46656=6a+15b+20c+15d+6e+f  より、
                 f=46656−6−930−10800−23400−10800=720

なので、

 x6=1・F1(x)+62・F2(x)+540・F3(x)+1560・F4(x)+1800・F5(x)+720・F6(x)

 x7=a・F1(x)+b・F2(x)+c・F3(x)+d・F4(x)+e・F5(x)+f・F6(x)+g・F7(x) とおくと、

上記の表より、

 1=a
 128=2a+b  より、 b=126
 2187=3a+3b+c  より、 c=2187−3−378=1806
 16384=4a+6b+4c+d  より、 d=16384−4−756−7224=8400
 78125=5a+10b+10c+5d+e  より、
                   e=78125−5−1260−18060−42000=16800
 279936=6a+15b+20c+15d+6e+f  より、
          f=279936−6−1890−36120−126000−100800=15120
 823543=7a+21b+35c+35d+21e+7f+g  より、
   g=823543−7−2646−63210−294000−352800−105840=5040

なので、

 x7=1・F1(x)+126・F2(x)+1806・F3(x)+8400・F4(x)+16800・F5(x)
                                  +15120・F6(x)+5040・F7(x)

 ちょっと手計算では辛くなってきたので、以下は、Excel さんに手伝ってもらおう。

n 1 2 3 4 5 6 7 8 9
a 1 1 1 1 1 1 1 1 1
b 0 2 6 14 30 62 126 254 510
c 0 0 6 36 150 540 1806 5796 18150
d 0 0 0 24 240 1560 8400 40824 186480
e 0 0 0 0 120 1800 16800 126000 834120
f 0 0 0 0 0 720 15120 191520 1905120
g 0 0 0 0 0 0 5040 141120 2328480
h 0 0 0 0 0 0 0 40320 1451520
i 0 0 0 0 0 0 0 0 362880

 この表より、

 x8=1・F1(x)+254・F2(x)+5796・F3(x)+40824・F4(x)+126000・F5(x)
                    +191520・F6(x)+141120・F7(x)+40320・F8(x)

 x9=1・F1(x)+510・F2(x)+18150・F3(x)+186480・F4(x)+834120・F5(x)
    +1905120・F6(x)+2328480・F7(x)+1451520・F8(x)+362880・F9(x)

 この計算結果は、S(H)さんのものと一致する。(ほっと、安心...!)

 ところで、 P(x)=a+b・F1(X)+c・F2(X)+・・・+d・F(X) の各係数は、連立方程式
を解くことにより得られたが、次のような方法があることをS(H)さんよりご教示いただいた。

 差分の考え方を用いる。下記の表は、ニュートン以来の差分の並べ方とのことである。

0      
1−a0
1 2−2a1+a0
2−a1 3−3a2+3a1−a0
2 3−2a2+a1
3−a2
3

何となく、(a−b) の展開公式に似ている! ここで、

Δa=an+1−a 、 Δ2=Δan+1−Δa 、 ・・・ 、 Δk=Δk-1n+1−Δk-1

とおくと、上記の表は、次のように整理される。

0      
Δa0
1 Δ20
Δa1 Δ30
2 Δ21
Δa2
3

 このとき、次の事実が知られている。

 関数 F(x)=x について、 a=F(n) で数列 { a } を定める。

  x = a0+Δa0x+Δ20x(x−1)/2!+Δ30x(x−1)(x−2)/3!+・・・

が成り立つ。


 n=3 の場合に確認してみよう。

  x3=a+bx+cx(x−1)+dx(x−1)(x−2) とおく。

 x=0 のとき、 a0=a

 x=1 のとき、 a1=a+b

 x=2 のとき、 a2=a+2b+2c

 x=3 のとき、 a3=a+3b+6c+6d

  以上の計算から、 b=Δa0 、 b+2c=Δa1 なので、 2c=Δ20

 同様にして、 b+4c+6d=Δa2 なので、 2c+6d=Δ21  よって、 6d=Δ30

 したがって、

   x3=a0+Δa0x+Δ20x(x−1)/2!+Δ30x(x−1)(x−2)/3!

と書けることが示された。

 この展開式を用いると、

  x3=1・F1(x)+3!・F2(x)+3!・F3(x)=1・F1(x)+6・F2(x)+6・F3(x)

 すなわち、 x3・F1(x)+・F2(x)+・F3(x) における係数は、次の差分の計算
から直ちに得られる。

     
12
19
27

 読者の方も

  x4=1・F1(x)+14・F2(x)+36・F3(x)+24・F4(x)

  x5=1・F1(x)+30・F2(x)+150・F3(x)+240・F4(x)+120・F5(x)

について、差分を利用して確認してみて下さい。

 実際に、

       
14
15 36
16 50 24
65 60
81 110
175
256
 
         
30
31 150
32 180 240
211 390 120
243 570 360
781 750
1024 1320
2101
3125

(コメント) やっている計算はほとんど連立方程式の計算と同等ですが、何となくスッキリで
      すね!


 S(H)さんの計算によれば、

 n9−n3=504F2(x)+18144F3(x)+186480F4(x)+834120F5(x)

        +1905120F6(x)+2328480F7(x)+1451520F8(x)+362880F9(x)

と書けるので、各係数が9の倍数であることから、n9−n3 は、9の倍数となる。


 x を、{ 1,F1(x),F2(x),・・・,F(x) } で表す問題は、当HPの「ベル数」でも取り上げ
られた。
(平成21年4月19日付けで、S(H)さんより、ご指摘いただきました!謝謝!)

 x の関数 Pk(x) ( k は、自然数)を

    k(x)=x(x−1)・・・(x−k+1)

と定義する。このとき、 k(n)= である。 特に、 (n)=n! である。

 ここで、 0=1 であるので、 0(x)=1と約束することは理にかなったものだろう。

 上記で考えた整数値多項式 F(x) との関係は、明らかに、 k(x)=k!・F(x)

 この Pk(x) (k=1、2、3、・・・) を用いて、多項式 (x+1) が表される。

 例えば、

  (x+1)3=x(x−1)(x−2)+6x(x−1)+7x+1=P3(x)+6P2(x)+7P1(x)+P0(x)

 このとき、x に、x−1 を代入すると、

  x3=(x−1)(x−2)(x−3)+6(x−1)(x−2)+7(x−1)+1

なので、両辺に x を掛けると、

  x4=x(x−1)(x−2)(x−3)+6x(x−1)(x−2)+7x(x−1)+x

   =P4(x)+6P3(x)+7P2(x)+P1(x)

   =24・F4(x)+36・F3(x)+14・F2(x)+F1(x)

   =1・F1(x)+14・F2(x)+36・F3(x)+24・F4(x)

 この結果は、上記で得られたものと一致する。

 このように、基底の変換の係数は、第2種スターリング数からも得られる点が興味深い。

(コメント) この第2種スターリング数との関係から、整数値多項式の定理の名前に、「ポ
      リア」がつくものがあることを、思わず合点してしまいました。

 平成21年4月22日付けで、S(H)さんが、幾つかの問題を提起された。

1.Determine the greatest common divisor of the elements of
 the set { n13−n | n∈Z }.
                     (
[PJ pp.110] UC Berkeley Preliminary Exam 1990

2.What is the greatest common divisor of the set of numbers
 { 16+10n−1 | n=1、2、・・・ }?


3.Suppose that p is a prime number and is greater than 3.
 Prove that 7−6−1 is divisible by 43.         
Iran 1994

 その中の「Berkeley」という文字に惹かれ、まず、1.の問題を考えてみようと思う。

 東京工業大学の問題のように、いくつか実験をしてみよう。

  n=1 のとき、 n13−n=0

  n=2 のとき、 n13−n=8192−2=8190=2・32・5・7・13

  n=3 のとき、 n13−n=1594323−3=1594320=24・3・5・7・13・73

と計算してみると、 2・3・5・7・13=2730 の倍数となっているような...予感!

 実は、n13−n は、2730 で割り切れることが次のように示される。2730 が求める最
大公約数(greatest common divisor)であることは明らかだろう。

 フェルマーの定理を用いるのがエレガントかな?

(証明) フェルマーの定理により、

   n2≡n (mod 2) 、n3≡n (mod 3) 、n5≡n (mod 5) 、

   n7≡n (mod 7) 、n13≡n (mod 13)

 が成り立つ。 ところで、

  n13−n=n(n12−1)=(2−n)(n11+n10+・・・+n+1)≡0 (mod 2)

  n13−n=n(n12−1)=(3−n)(n10+n8+・・・+n2+1)≡0 (mod 3)

  n13−n=n(n12−1)=(5−n)(n8+n4+1)≡0 (mod 5)

  n13−n=n(n12−1)=(7−n)(n6+1)≡0 (mod 7)

  n13−n≡0 (mod 13)

 なので、n13−n は、2、3、5、7、13 すなわち、2730 で割り切れる。  (証終)

 次に、2.の問題を考えてみよう。 1.と同様に、まず実験してみよう。

  n=1 のとき、 16+10n−1=16+10−1=25=52

  n=2 のとき、 16+10n−1=256+20−1=275=52・11

と計算してみると、 52=25 の倍数となっているような...予感!

 実は、16+10n−1 は、25 で割り切れることが次のように示される。25 が求める
最大公約数(greatest common divisor)であることは明らかだろう。

 1.とは異なる手法で解いてみよう。

(解) F(n)=16+10n−1 とおくと、

   F(n+1)−F(n)=16n+1+10(n+1)−1−(16+10n−1)

              =15・16+10

              =15・(15+n・15n-1+・・・+n・15+1)+10

              =15n+1+n・15+・・・+n・152+25

              =25(9・15n-1+9n・15n-1+・・・+9n+1)

  は、25 で割り切れる。

  このとき、F(n)=16+10n−1 が25 で割り切れることが数学的帰納法により示

 される。

  n=1 のとき、 F(1)=16+10−1=25 は、25 で割り切れる。

   よって、 n=1 のとき成り立つ。

  n=k (k≧1) のとき成り立つと仮定する。すなわち、

    F(k)=16+10k−1 は25 で割り切れる。

  n=k+1 のとき、 F(k+1)−F(k)は、25 で割り切れ、かつ、F(k) が25 で割り

   切れるので、F(k+1)は、25 で割り切れる。

   よって、n=k+1 のときも成り立つ。

 以上から、数学的帰納法により、すべての自然数 n に対して、

          F(n)=16+10n−1 が25 で割り切れる。  (終)

 最後に、3.を考えてみる。例によって、実験してみよう。 p は、3以上の素数なので、

  p=5 のとき、 75−65−1=16807−7776−1=9030=2・3・5・7・43

  p=7 のとき、 77−67−1=823543−279936−1=543606=2・3・72・432

  p=11 のとき、 711−611−1=1977326743−362797056−1
                      =1614529686=2・3・7・11・43・67・1213

  p=13 のとき、 713−613−1=83828316390=2・3・5・7・13・432・16607

  p=17 のとき、 717−617−1=215703854542470
                      =2・3・5・7・17・43・2389・588173

 p=19 のときは、Excel さんが、オーバーフローになってしまい計算ができなかった。

 何となく上記の計算から、2・3・7・43=1806 の倍数となっているような...予感!
はするが、前の問題達のように確証できないところが口惜しい。

 もっとも、問題は、「43で割り切れる」ことを示せばいいので、それほど深入りしなくても
よいのかな?

 因みに、

  p=3 のとき、 73−63−1=343−216−1=126

  p=2 のとき、 72−62−1=49−36−1=12

から、「43で割り切れる」ことを示すために、「素数 p>3」という条件は外せない。

     (解答準備中)


 平成21年4月24日付けで、S(H)さんが、新たに幾つかの問題を提起された。

1.Prove that 17−12−24+19 is divisible by 35, for any
 natural number n.


 (Get the divisor d such that d|17−12−24+19 for any natural number n.

2.Prove the following :

 (1) 36n−26n is divisible by 35,for every positive integer n ;

 
Get the divisor d such that d|36n−26n for every positive number n.)

 (2) n5−5n3+4n is divisible by 120,for every integer n ;

 
Get the divisor d such that d|n5−5n3+4n for every integer n.)

 (3) for all integers m and n ,mn(m60−n60) is divisible
    by 56786730.
                 
(Hint : 56786730=2・3・5・7・11・13・31・61.)

 (4) Prove that n2+3n+5 is never divisible by 121 for any
    positive integer n


(1.の解) n=1 のとき、 17−12−24+19=0 なので、すべての自然数で割

      り切れる。

    n=2 のとき、 17−12−24+19=−70=−35・2

    n=3 のとき、 17−12−24+19=−3780=−35・22・33

    n=4 のとき、 17−12−24+19=−138670=−35・2・7・283

       ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 素因数の状況を表にしてみると、

 
・・・
素因数  とその巾 2 ・・・
素因数 3 とその巾 3 ・・・
素因数  とその巾 2 ・・・
素因数  とその巾 ・・・
その他の素因数 283 ・・・

 このことから、すべての自然数 n に対して、17−12−24+19 は、

     2 、 5 、 7 、10 、14 、35 、70

で割り切れることが予想される。

  (イ) 17−12−24+19 が、2 で割り切れることの証明

     17−12−24+19≡1−0−0+1=2≡0 (mod 2) より、明らか。

  (ロ) 17−12−24+19 が、5 で割り切れることの証明

     17−12−24+19≡2−2−(−1)+(−1)=0 (mod 5) より、明

    らか。

  (ハ) 17−12−24+19 が、7 で割り切れることの証明

     17−12−24+19≡3−(−2)−3+(−2)=0 (mod 7) より、明

    らか。

  (ニ) 17−12−24+19 が、10 で割り切れることの証明

     (イ)、(ロ) より、明らか。

  (ホ) 17−12−24+19 が、14 で割り切れることの証明

     (イ)、(ハ) より、明らか。

  (ヘ) 17−12−24+19 が、35 で割り切れることの証明

     (ロ)、(ハ) より、明らか。

  (ト) 17−12−24+19 が、70 で割り切れることの証明

     (ハ)、(ニ) より、明らか。

   以上から、 すべての自然数 n に対して、17−12−24+19 は、

     2 、 5 、 7 、10 、14 、35 、70

  で割り切れる。

(2.(1)の解) 36n−26n=729−64≡(−1)−(−1)=0 (mod 5)

         36n−26n=729−64≡1−1=0 (mod 7)

     以上から、 すべての自然数 n に対して、36n−26n は、35 で割り切れる。

  ところで、 n=1 のとき、 36n−26n=729−64=665=5・7・19

 n=2 のとき、 36n−26n=7292−642=527345=5・7・13・19・61

 n=3 のとき、 36n−26n=7293−643=387158345=5・7・19・577・1009

 n=4 のとき、 36n−26n=7294−644=282412759265
                  =5・7・13・19・61・97・5521

     ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 上記の計算から、すべての自然数 n に対して、36n−26n は、

     5 、 7 、19 、35 、95 、133 、665

の各数で割り切れることが予想される。(5、7 については、証明済み)

 36n−26n が 19 で割り切れることは、

      36n−26n=729−64≡7−7=0 (mod 19)

より明らかだろう。

 以上から、 すべての自然数 n に対して、36n−26n は、

     5 、 7 、19 、35 、95 、133 、665

の各数で割り切れる。


(2.(2)の解)  n5−5n3+4n=(n−2)(n−1)n(n+1)(n+2) は連続する5整数

         の積である。

    n≧2のとき、 n5−5n3+4n=5!・n+25 で、n+25 は整数なので、

      n5−5n3+4n は、5!=120 で割り切れる。

    n=0、1 のときは、 n5−5n3+4n=0 で、もちろん、120 で割り切れる。

    負の整数 n については、 n=−m (mは自然数) として、同様に示される。

   以上から、 すべての整数 n に対して、n5−5n3+4n は、120 で割り切れる。

    n=3 のとき、 n+25=1 なので、すべての整数 n に対して、n5−5n3+4n を

   割り切る数は、120の約数全てである。



 平成21年5月2日付けで、S(H)さんが、新たな問題を提起された。

 1983+21983+31983+・・・+19861983≡0 (mod 1987)を示せ。

 一見すると難しそうな雰囲気だが、次のように考えれば易しいだろう。

 1987 は素数で、1983と1987は互いに素である。

 このとき、 19861983≡(−1)1983≡−11983 (mod 1987)

        19851983≡(−2)1983≡−21983 (mod 1987)

        19841983≡(−3)1983≡−31983 (mod 1987)

           ・・・・・・・・・・・・・・・・・・・・

        9941983≡(−993)1983≡−9931983 (mod 1987)

 よって、

  11983+21983+31983+・・・+9931983+9941983+・・・+19861983

 ≡11983+21983+・・・+9931983−9931983−・・・−21983−11983

 =0 (mod 1987)

 したがって、

  11983+21983+31983+・・・+9931983+9941983+・・・+19861983

 は1987で割り切れる。

(コメント) 類題がたくさん作れそう...。


 DD++さんからのコメントです。(平成28年1月5日付け)

 任意の正の整数nに対し、a[n] = 19n+2*(-16)n-1 が 7の倍数であることを示せ。

 これは、東京工業大(1986年)の問題

 整数 a=19+(−1)n-14n-3 (n=1、2、3、・・・)のすべてを割り切る素数を
求めよ。


と同じ趣旨のもの。略証ですが、とりあえず受験での常套手段2種4つ。

[解法1]・・・(合同式利用)

 a[n] = 19n+2*(-16)n-1 ≡ 5n + 2*5n-1 ≡ 7*5n-1 ≡ 0 (mod 7)

[解法2-1]・・・(数学的帰納法利用 その1)

 19k+1+2*(-16)k =  19{19k+2*(-16)k-1} - 7*10*(-16)k-1 と  191+2*(-16)0 = 7*3 から帰
納的に成立。

[解法2-2]・・・(数学的帰納法利用 その2)

 19k+1+2*(-16)k = 7*5*19k - 16{19k+2*(-16)k-1} と 191+2*(-16)0 = 7*3 から帰納的に
成立。

[解法2-3]・・・(数学的帰納法利用 その3)

 x2 = 3x+304 の解が、x = 19、-16 であるので、

19k+2+2*(-16)k+1 = 3{19k+1+2*(-16)k} + 304{19k+2*(-16)k-1} と 191+2*(-16)0 = 7*3 と
192+2*(-16)1 = 7*47 から帰納的に成立。


 S(H)さんから新しい問題が出題されました。(平成28年1月7日付け)

 23n−7n−1は、49の倍数であることを証明せよ。


 DD++さんからのコメントです。(平成28年1月7日付け)

 23n−7n−1=(Σk=1〜n 7・8k-1 ) −7n ≡ ( Σk=1〜n 7 ) −7n =0  (mod 49)


(コメント) 23n−1=Σk=1〜n 7・8k-1 という発想が素晴らしいですね!なかなか思いつき
      ません。あとは、7・8k-1=7・(7+1)k-1≡7  (mod 72) という合同式特有の式
      変形から明らかですね。


 S(H)さんからさらなる試練をいただきました。(平成28年1月10日付け)

(1) Prove that 8^n - 3^n is divisiible by 5 for all natural numbers n
(2) Prove that 11^n + 8^n - 3^n is divisiible by 4 for all natural numbers n
(3) Prove that 2*13^n + 11^n + 8^n - 3^n is divisiible by 2 for all natural numbers n

 S(H)さんからは、線型漸化式を作る発想で証明せよとのことであるが、数学的帰納法が
手っ取り早い気がする。

(1)の証明: n=1のとき、8^1 - 3^1=5 より、5の倍数となり、n=1のとき成り立つ。

 n=k(k≧1)のとき成り立つと仮定する。すなわち、 8^k - 3^k は5の倍数。

  このとき、 8^k - 3^k=5n (nは整数) とおけるので、 8^k = 3^k+5n

  よって、 8^(k+1) - 3^(k+1)=8(3^k+5n)- 3^(k+1)=5・3^k+5(8n) は5の倍数となり、

 命題は、n=k+1の時も成り立つ。

 したがって、すべての自然数nに対して、8^n - 3^n は5の倍数 (証終)

 (2)(3)も同様に、数学的帰納法で示される。


 DD++さんからのコメントです。(平成28年1月11日付け) 

 (3)については、数学的帰納法を用いなくても次のように示されます。

 nの偶奇にかかわらず、4つの項のうち、偶数が2つで奇数も2つあるので、合計は偶数。



   以下、工事中