気になった問題

質問

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

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

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

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

回答No.4

yoikagari · ベストアンサー

他の方がおっしゃる通り
(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)の場合はもう少し簡単になります。

お礼

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

回答No.3

sunasearch

５で割ったときのあまりは、下一桁だけを考えればよいので、
nもn+20も５で割ったときのあまりは同じになりますから、
問題は、n^nを５で割った余りと、
n^(n+20)を５で割った余りが等しくなることを示せばよくなります。

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

n^a と n^(a+4) を５で割ったときの余りが等しくなります。
ここで、aをnに置き換えれば証明できると思います。

お礼

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

回答No.2

ringohatimitu

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

回答No.1

ringohatimitu

modで上手くいきます。
(n+20)^(n+20)=(n^n)*(n^20) (mod 5)　で すべての整数nに対して　n^4=1 (mod 5)　であることに注意すると（最初の式）=n^n (mod 5)　となります。これは余りが等しいことを表しています。

お礼

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