次の問題が気になって気になって仕方ありません.
どなたかご教授いただけないでしょうか?
(この問題は課題やレポートのテーマではありません)

「n^nを5で割った余りをf(n)とする(ただし,nは正の整数).
このとき,f(n)=f(n+20)を証明せよ」という問題です.

数学的帰納法やmodで試したのですが,なかなかうまくいきません.

よろしくお願いいたします.

A 回答 (4件)

他の方がおっしゃる通り


(n+20)^(n+20)≡n^(n+20) (mod 5)ですから、

n^(n+20)とn^nを5で割った余りが等しいことがいえればいいのです。

それには
n^(n+20)-n^n=(n^n)*(n^20-1)=(n^n)*(n^4-1)*(n^16+n^12+n^8+n^4+1)
ですから(n^n)*(n^4-1)が5で割り切れることがいえればいいのです。

(1)
nが5で割り切れるとき
n^n≡0^n≡0 (mod 5)ですので当然(n^n)*(n^4-1)≡0 (mod 5)です。

(2)
nが5で割り切れないとき
n≡1、4 (mod 5)のとき、4≡-1 (mod 5)ですから
n≡±1 (mod 5)と書くことが出来ます
よって、n^4-1≡(±1)^4-1≡1-1≡0 (mod 5)

n≡2、3 (mod 5)のとき、3≡-2 (mod 5)ですから
n≡±2 (mod 5)と書けます
よって、n^4-1≡(±2)^4-1≡16-1≡15≡0 (mod 5)

よってnが5で割り切れないとき、n^4-1は5で割り切れます。
したがって、このときも(n^n)*(n^4-1)≡(n^n)*0≡0 (mod 5)となります。

(1)、(2)のいずれの場合も、(n^n)*(n^4-1)≡0 (mod 5)がいえました。

したがって、任意の自然数nに対して
n^(n+20)-n^n≡(n^n)*(n^4-1)*(n^16+n^12+n^8+n^4+1)
≡0*(n^16+n^12+n^8+n^4+1)≡0 (mod 5)となることが示されました。


P.S.
ringohatimituさんが言うように
フェルマーの小定理
pを素数、nをpで割り切れない整数とするとn^(p-1)≡1 (mod p)
を使ってよいのなら(2)の場合はもう少し簡単になります。
    • good
    • 0
この回答へのお礼

ありがとうございました.
フェルマーの小定理.
6年ぶりに聞きます.
大変参考になりました.

お礼日時:2005/04/16 20:47

5で割ったときのあまりは、下一桁だけを考えればよいので、


nもn+20も5で割ったときのあまりは同じになりますから、
問題は、n^nを5で割った余りと、
n^(n+20)を5で割った余りが等しくなることを示せばよくなります。

一桁の数字を4乗したときに、その下一桁は、もとの数字に一致しますから、

n^a と n^(a+4) を5で割ったときの余りが等しくなります。
ここで、aをnに置き換えれば証明できると思います。
    • good
    • 0
この回答へのお礼

ありがとうございました.
確かにそうですよね.
余りだけに注目すればいいんですよね.

お礼日時:2005/04/16 20:45

(訂正)下の回答ですべての整数に対してではなくて0以外の整数に対してでした。

    • good
    • 0

modで上手くいきます。


(n+20)^(n+20)=(n^n)*(n^20) (mod 5) で すべての整数nに対して n^4=1 (mod 5) であることに注意すると(最初の式)=n^n (mod 5) となります。これは余りが等しいことを表しています。
    • good
    • 0
この回答へのお礼

ありがとうございました.
やはりmodでうまくいきますよね.
参考になりました.

お礼日時:2005/04/16 20:44

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報