◆広島県 清川 育男さんからの解答。
オイラーの定理の特殊形フェルマー定理によると
（ｎ，ｒ）＝１のとき
ｎｒ−１≡１（mod r)
したがって、（ｎｒ−１−１）はｒで割り切れる。
以上です。
これでは、あまり面白くないですね。
だからといって、オイラーの定理かフェルマーの定理を知らないと、解くのは無理でしょうね。
【コメント】
ご指摘の通りですが、たぶんこの問題はそれを証明して欲しいという意図だと思います。
【コメントの追加】
出題者から、「オイラーの定理やフェルマーの定理を使わないで、高校数学の範囲で解いて下さい。」 というコメントがありました。
◆石川県 数学好き さんからの解答。
|
◆補題
ａｎ≡ｂｎ (mod ｒ)、ｎとｒは互いに素とすると、
∵ａｎ≡ｂｎ (mod ｒ)だから、 ｎとｒは互いに素だから、ａ−ｂはｒで割り切れる。 つまりａ≡ｂ (mod ｒ) |
◆証明
ｒ−１個の数、ｎ、２ｎ、３ｎ・・(ｒ−１)ｎを考える。
このｒ−１個の数をｒで割ると、その余りの中に１からｒ−１の数が１個ずつ表れる。
これらを掛け合わせると、
ｎ×２ｎ×３ｎ･･･×(ｒ−１)ｎ≡１×２×３･･･×(ｒ−１) (mod ｒ)
つまり(ｒ−１)！ｎr-1≡(ｒ−１)！ (mod ｒ)
ｒは素数なので、(ｒ−１)！とｒは互いに素である。
したがって補題より、ｎr-1≡１ (mod ｒ)
◆千葉県 Lily of the valley さんからの解答。
問題は gcd(n,r)=1 のとき
nr-1 ≡ 1 (mod.r) を証明すればよい。
ここで、nr ≡ n (mod.r) …(*)
を証明できれば、gcd(n,r)=1 より、両辺を n でわって
nr-1 ≡ 1 (mod.r) がしめされる。
ゆえに、これを n に関する帰納法でとく。
まず、n=1 のとき (*)は真である。
ここで、n=k のときの成立を仮定すると、
kr ≡ k である。このとき、二項定理より
| (k+1)r= | r Σ i=0 | r! ―――― i!(r-i)! | ki |
ここで、r が素数ということより、1＜i＜r のとき
| r! ―――― i!(r-i)! | ≡0 (mod.r) |
[ gcd(r,i!)=1, gcd(r,(r-i)!)=1 をもちいる。]
よって、(k+1)r ≡ kr＋1 (mod.r)
ここで仮定より、kr＋1 ≡ k+1 (mod.r)
よって、k+1 のときも(*)は真。
ゆえに、命題は示された。
(感想)ひょんな所で出てくる二項定理。これを使うと、
| d ―― dx | (ax+b)n = an(ax+b)n-1 |
が、 数２までの範囲で(微分の定義にしたがう程度)でしめされるんですよね。
高校生のときそのことを証明して、うれしくなった思い出があります。