この数学の問題が解けません。大学受験レベル

質問

19^n + (-1)^(n-1) * 2^(4n-3)
n=(1,2,3,…)
のすべてを割り切る素数を求めよ。

答え自体は簡単に７ということがわかりますが

すべての場合に成り立つという証明のために
「nの値が何であっても７で割り切ることが可能」

と言うことを示さなければなりません。

a^p - a は p で割り切れるという公式を使って証明をするのですが、
その方法がわかりません。

どなたか証明できる方はいますか？

回答No.6

Mr_Holland · ベストアンサー

7を法とする合同式で考える方法はいかがでしょうか。

　19^n + (-1)^(n-1)*2^(4n-3)
=19^n + (-1)^(n-1)*16^n/8
=19^n + 2*(-16)^(n-1)
=(21-2)^n + 2*(-14-2)^(n-1)
≡(-2)^n + 2*(-2)^(n-1)　　　　　(mod 7)
=(-2)^n-(-2)^n
=0

　∴　19^n + (-1)^(n-1)*2^(4n-3)　は素数７で割り切れる。

お礼

この方法単純で簡単な証明でわかりやすかったです。
ありがとうございました

回答No.9

momordica

こんなのはどうでしょうか。

a(n)=19^n + (-1)^(n-1) * 2^(4n-3) とおくと、

　a(n)=(21-2)*19^(n-1) +(-1)^(n-1) *2*2^(4n-4)
　　=21*19^(n-1) -2*19^(n-1) +2* (-1)^(n-1) *(2^4)^(n-1)
　　=21*19^(n-1) -2*19^(n-1) +2*(-16)^(n-1)
　　=21*19^(n-1) -2*{19^(n-1)-(-16)^(n-1)}

ここで、n≧2のとき、
　19^(n-1)-(-16)^(n-1)
　　={19-(-16)}*Σ[k=0 to (n-2)]{19^k *(-16)^(n-2-k)}
　　=35*Σ[k=0 to (n-2)]{19^k *(-16)^(n-2-k)}
なので、
　a(n)=21*19^(n-1) -2*35*Σ[k=0 to (n-2)]{19^k *(-16)^(n-2-k)}
　　=7*{ 3*19^(n-1) -10*Σ[k=0 to (n-2)]{19^k *(-16)^(n-2-k)} }

また、n=1のとき
　a(1)=21=7*3

よって、任意の自然数ｎについて、a(n)は7で割り切れる。

お礼

Σを使う方法ですか。
自分で考えるのは難しそうですが、書いてあることはよくわかりました。
ありがとうございました。

回答No.8

htms42

１９^n＝(２１－２)^n＝２１＊Ａ＋(－２)^n

(－２)^n＋(－１)^(n-1)＊２^(4n-3)
＝(－２)^n＊(１－２^(３ｎ－３))
＝(－２)^n＊(１－８^(ｎ－１))
＝(－２)^n＊(１－(７＋１)^(ｎ－１))
＝(－２)^n＊(１－７＊Ｂ－１)
＝－７＊Ｂ＊(－２)^n

与式＝２１＊Ａ－７＊Ｂ＊(－２)^n＝７＊Ｃ

こんなのでどうでしょう。
２項展開の一般式は使っています。

お礼

ん。これけっこう難しいですね。
すぐには理解できませんでしたが、少ない行数で証明することが出来るのですね。
ありがとうございました

回答No.7

dolzark

今ざっと計算してみました。
この方法で証明できる確証はありませんが、参考程度に。

数学的帰納法を使います。数列はa(n)とします。
n = 1 のとき、a(1) = 21 なので7で割り切れます。

n ≧ 2 の時、a(n+1) - a(n) が7で割り切れることを示します。
天下り的に「7で割り切れるはずだ」という方針で行くなら合同式で変形し、a(n+1) - a(n) ≡ 0 (mod7) を示せばいいはずです。

合同式の性質として、「累乗は多くても(mod-1)回でループになる」というものがあります。今回はmod7なので、多くとも6回以内にループするはずです。
計算したら19^n（≡5^n）は6回でループ、(-1)^nは2回でループ、2^4n（＝16^n≡2^n）は3回でループしました。よってa(n+1) - a(n) ≡ a(n+7) - a(n+6) (mod7) が成り立ちます。
ということは、nの値が「6の倍数」「6の倍数+1」「6の倍数+2」…「6の倍数+5」の6通りを計算して、全部≡0になれば証明できたことになる…はずです。

かなり力づくな解法なので、作為解ではないと思います。
a^p - a は p で割り切れるという公式を使った証明は僕には分かりません…もっとエレガントな解法があるのでしょうか。

お礼

modは趣味で調べたことがあるだけなので
こんな法則があるとは初耳でした。
とても興味深い回答でした。
ありがとうございました

回答No.5

Tacosan

それを無理に使いたいなら n = 1～6 まで努力と根性で試して, あとは
(n のとき) - (n-6 のとき)
を考えるんだろうが... そもそも「大学受験」で
「a^p - a は p で割り切れる」
ことを使っていいのか?

お礼

実はこの問題小説にのってまして、

参考文献的なところをみるとに国立大学入試に出たらしいのです。

で、小説の主人公が
「a^p - a は p で割り切れる」
を使って解けばいいということを言っていたので、質問しました。

数学的帰納法で解く方法はなんとかわかったんですけど。

回答ありがとうございました

回答No.4

gohtraw

ｎ＝１のとき与式＝１９＋２＝２１なので、その素因数は３と７です。
ｎ＝ｋのとき与式が７の倍数であるとすると、
１９＾ｋ＋（－１）＾（ｋ－１）＊２＾（４ｋ－３）＝７ｍ
と表され、（－１）＾（ｋ－１）＊２＾（４ｋ－３）＝ｒとおくと
１９＾ｋ＋ｒ＝７ｍと表されます。・・・（１）
一方ｎ＝ｋ＋１のとき与式は
１９＾（ｋ＋１）＋（－１）＾（ｋ）＊２＾（４ｋ＋１）＝１９＾（ｋ＋１）－１６ｒ
と表されます。・・・（２）
（１）より　１９＾ｋ＝７ｍ－ｒ　なので　１９＾（ｋ＋１）＝１９＊７ｍ－１９ｒ
です。これを（２）に代入すると与式の値は
１９＾（ｋ＋１）－１６ｒ＝１９＊７ｍ－３５ｒ
　　　　　　　　　　　　＝７（１９ｍ－５ｒ）
吟味は必要かもしれませんが、方法としてはこれでいけるのではないでしょうか？
３で割りきれるかどうかはｎ＝ｋの時の与式の値を３ｐとおくとｎ＝ｋ＋１のときの
与式の値は１９＊３ｐ－３５ｒとなりますがｒの素因数は２のみなので、与式は３で
割りきれないことが示せると思います。

お礼

数学的帰納法ですね。

この方法は自分でも何とか解けましたが、
自分のよりわかりやすく解いていますね。

ありがとうございました

回答No.3

R_Earl

> a^p - a は p で割り切れるという公式を使って証明をするのですが、

この公式を使わなくても数学的帰納法で示せそうです。

19^k + {(-1)^(k-1)}{2^(4k-3)}が7の倍数と仮定し、
19^(k+1) + {(-1)^k}{2^(4n+1)}が7の倍数である事を示してみます。

19^k + {(-1)^(k-1)}{2^(4k-3)} = 7mとおき、両辺を19倍すると

19^(k+1) + 19{(-1)^(k-1)}{2^(4k-3)} = 19・7m　… (1)

これで19^(k+1)が作れました。あとは{(-1)^k}{2^(4n+1)}を作るために、
19{(-1)^(k-1)}{2^(4k-3)}の項を次のように変形します。

19 = (-1)・2^4 + 35なので
19{(-1)^(k-1)}{2^(4k-3)}
= {(-1)・2^4 + 35}・{(-1)^(k-1)}{2^(4k-3)}
= {(-1)^k}{2^(4n+1)} + 35{(-1)^(k-1)}{2^(4k-3)}

これで無理矢理{(-1)^k}{2^(4n+1)}を作りだしました。
この結果を(1)に代入すると

19^(k+1) + 19{(-1)^(k-1)}{2^(4k-3)} = 19・7m
19^(k+1) + {(-1)^k}{2^(4n+1)} + 35{(-1)^(k-1)}{2^(4k-3)} = 19・7m

これで左辺に作りたかった19^(k+1) + {(-1)^k}{2^(4n+1)}が揃いました。
後は余分な項を右辺に移すと

19^(k+1) + {(-1)^k}{2^(4n+1)} = 19・7m - 35{(-1)^(k-1)}{2^(4k-3)}

ここで右辺は7で因数分解できるので、

19^(k+1) + {(-1)^k}{2^(4n+1)} = 7[19m - 5{(-1)^(k-1)}{2^(4k-3)}]

よって19^(k+1) + {(-1)^k}{2^(4n+1)} も7の倍数となりました。

お礼

丁寧に帰納法を教えていただきありがとうございます。
おかげで良く分かりました。

回答No.2

naniwacchi

こんばんわ。
だいぶ、むかーしの入試問題だったような記憶がありますね。＾＾

＞「nの値が何であっても７で割り切ることが可能」
単純には、帰納法で示すことができます。
19^nを「隠してしまう」ような変形を考えれば、難しくありませんよ。

お礼

帰納法を使って解く方法なら自分でも出来ました。

ただ、「a^p - a は p で割り切れる」を使って解くというからには

もっと単純に解けるのではないかと思って。

ありがとうございました

回答No.1

koko_u_u

もっと単純に、数列 19^n や 2^(4n-3) が mod 7 でどのように推移するかを観察するべきです。

お礼

mod7
で解いてくれた方がいてくれて簡単に解ける事が理解できました。

ありがとうございました