数論の演習問題(解答)

　ちと早いけど,昨日出した問題の解答を与えておきます。あまりスマートではなく泥臭い解答となりましたが,もっとエレガントな方法があればコメントで披露してください。

問１．(2¹⁰⁰－1)⁹⁹を100で割ったときの余りを求めよ。（ヒントは 2¹⁰＝1024でこれを100 で割った余りは24であるということです。）

(解答) まず, 2¹⁰＝1024≡24(mod 100 )です。そして, 24²＝576≡－24(mod 100)ですから,24³≡－24²≡24(mod100)...etc.になります。

　よって2¹⁰⁰≡24¹⁰≡－24(mod 100)です。それ故, 2¹⁰⁰－1≡－25(mod 100)ですね。

　次に(－25)²＝625≡25(mod 100)ですから,(2¹⁰⁰－1)⁹⁹≡(－25)⁹⁸・(－25)≡-25≡75(mod 100)である,というわけで,(2¹⁰⁰－1)⁹⁹を100で割った余りは75である,というのが結論です。(以上）

問2. 3³⁰≡1＋17・31 (mod  31²)であることを証明せよ。

(解答) "フェルマー(Fermat)の小定理"によれば,3³⁰≡1(mod31)です。

　よってＡ をある整数として,3³⁰＝31Ａ＋1と書けますから,Ａ≡ 17(mod31)となることを証明すればいいです。

　そこで,方針としては3¹⁵≡1(mod31)か,あるいは3¹⁵≡－1(mod31)であるかのいずれかなので,3¹⁵＝31Ｂ±1より,3³⁰＝(31Ｂ±1)²≡1±2Ｂ・31(mod 31²)として,±2Ｂ≡Ａ≡17(mod31)を示すことにします。

　そのために,まず3⁵＝243＝(31・8－5)と書き,両辺を３乗します。

　すなわち,3¹⁵＝(31・8－5)³＝(31・8)³－15(31・8)²＋75・31・8－125≡600・31－4・31－1≡7・31－1(mod 31²)ですが,これをまとめると3¹⁵≡7・31－1(mod 31²)となります。

　したがって,Ａ≡－2Ｂ＝－14≡17(mod31)となるので,結局,証明の結論である3³⁰≡1＋17・31(mod 31²)が得られました。(以上)

http://fphys.nifty.com/(ニフティ「物理フォーラム」サブマネージャー）                                       TOSHI 

http://blog.with2.net/link.php?269343(ブログ・ランキングの投票）↑ここをクリックすると投票したことになります。