2-1335:二次合同式...基本 ^^

画像:http://kishuji-minabe.jp/?p=2957 より 引用 Orz〜
DSC_0295.jpg

問題 2-1335・・・http://aozoragakuen.sakura.ne.jp/suuron/node37.html より 引用 Orz〜

次の合同方程式を解け.
(1)
$x^2+x+1\equiv 3\quad (\bmod.\ 25)$
(2)
$x^2\equiv 1\quad (\bmod.\ 39)$






































解答

・わたしの...

(1)
x^2+x-2≡0 (mod 25)
(x+2)(x-1)≡0
so...
x≡1, 23

(2)
(x+1)(x-1)≡0 (mod 39)
so...
x≡1 , 38

合同式ならではの解法に注意が必要でした...^^; Orz...

・鍵コメT様からのもの Orz〜


(1)は正しいですが,本当は,理由としてきちんとした考察が必要です.
2つの整数a,bの積が25(=5^2)で割り切れるのは,
・aが25の倍数
・bが25の倍数
・a,bがともに5の倍数
のケースが考えられます.
x+2とx-1は,その差が3であることから,ともに5の倍数となることはあり得ず,
したがって,積が25の倍数であれば,
x+2,x-1の一方が25の倍数と限ることになって,
x≡1,23 (mod 25)が得られるわけです.

(2)は,これではダメです.
x+1とx-1の積が39の倍数であっても,
「どちらかが39の倍数である」とは限りません.
「x+1,x-1の一方が3の倍数」かつ「x+1,x-1の一方が13の倍数」
となりますが,(1)とは違って,
例えば,「x+1が3の倍数で,x-1が13の倍数」である可能性はありますね.

結論は,x≡1,14,25,38 (mod 39)です.

*(2)は...1^2〜19^2までを実際に計算して求めるしかないのでしょうか知らん?

「x+1,x-1の一方が3の倍数」かつ「x+1,x-1の一方が13の倍数」だから,
(A)「x+1≡0 (mod 3)かつ x+1≡0 (mod 13)」
(B)「x+1≡0 (mod 3)かつ x-1≡0 (mod 13)」
(C)「x-1≡0 (mod 3)かつ x+1≡0 (mod 13)」
(D)「x-1≡0 (mod 3)かつ x-1≡0 (mod 13)」
のいずれかです.
(A)や(D)は,ただちにx+1≡0 (mod 39)となります.
(スモークマンさんのは,この場合のみを調べたことになっています.)

(B)であれば,法を39に揃えて
「13x+13≡0 (mod 39)…[1] かつ 3x-3≡0 (mod 39)…[2]」とし,
[1]-[2]*4からx+25≡0 (mod 39)を得て,x≡14 (mod 39)を得ます.

(C)も同様にできますし,2回解くのを避けて,
「x-1≡0 (mod 3)⇔(-x)+1≡0 (mod 3)」や「x+1≡0 (mod 13)⇔(-x)-1≡0 (mod 13)」
を利用し,(B)に帰着させることで,-x≡14 (mod 39)を得てもよいです.

このように,(別の問題でもコメントしましたが,)合同式の1次方程式は,
ユークリッドの互除法を用いてxの係数を1に近づける方法が定石と言えます.

*よくわかりました ^^♪

関連記事
スポンサーサイト



コメント

>鍵コメT様へ ^^

スモークマン
なるほど!!
よくわかりました ^^♪
紹介させていただきまっす〜m(_ _)m〜v

管理人のみ閲覧できます

-
このコメントは管理人のみ閲覧できます

>鍵コメT様へ ^^

スモークマン
そうか...^^;
(2)は...1^2〜19^2までを実際に計算して求めるしかないのでしょうか知らん?

管理人のみ閲覧できます

-
このコメントは管理人のみ閲覧できます
非公開コメント