« 数論の演習問題 | トップページ | 物理的仕事と生理的仕事 »

2006年9月28日 (木)

数論の演習問題(解答)

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

問1.(2100-1)99を100で割ったときの余りを求めよ。(ヒントは 210=1024でこれを100 で割った余りは24であるということです。)

(解答) まず, 210=1024≡24(mod 100 )です。そして, 242=576≡-24(mod 100)ですから,243≡-242≡24(mod100)...etc.になります。

 よって2100≡2410≡-24(mod 100)です。それ故, 2100-1≡-25(mod 100)ですね。

 次に(-25)2=625≡25(mod 100)ですから,(2100-1)99≡(-25)98・(-25)≡-25≡75(mod 100)である,というわけで,(2100-1)99を100で割った余りは75である,というのが結論です。(以上)

問2. 330≡1+17・31 (mod  312)であることを証明せよ。

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

 よってA をある整数として,330=31A+1と書けますから,A≡ 17(mod31)となることを証明すればいいです。

 そこで,方針としては315≡1(mod31)か,あるいは315≡-1(mod31)であるかのいずれかなので,315=31B±1より,330=(31B±1)2≡1±2B・31(mod 312)として,±2B≡A≡17(mod31)を示すことにします。

 そのために,まず35=243=(31・8-5)と書き,両辺を3乗します。

 すなわち,315=(31・8-5)3=(31・8)3-15(31・8)2+75・31・8-125≡600・31-4・31-1≡7・31-1(mod 312)ですが,これをまとめると315≡7・31-1(mod 312)となります。

 したがって,A≡-2B=-14≡17(mod31)となるので,結局,証明の結論である330≡1+17・31(mod 312)が得られました。(以上)

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

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

|

« 数論の演習問題 | トップページ | 物理的仕事と生理的仕事 »

303. 代数学・数論」カテゴリの記事

200. 問題・解答」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 数論の演習問題(解答):

« 数論の演習問題 | トップページ | 物理的仕事と生理的仕事 »