5011:合同式...

問題5011・・・水の流れさんのサイト  http://www2.ocn.ne.jp/~mizuryu/renzoku.html  より Orz~

問題1:次の合同式を解け。256x≡179(mod 337)

問題2:次の1次不定方程式を解け。

(1)39x+47y=4151   
(2)32x+57y-68z=1

問題3:次の連立合同式を解け
(1)2x+7y≡1(mod 13),5x+10y≡2(mod 13)
(2)x≡3(mod 5),x≡4(mod 7),x≡5(mod 9) 


















































解答

上記サイトより Orz~

・uchinyanさんのもの Orz~

問題1:
256x ≡ 179 (mod 337)
 337 は互いに素なので,mod 337 
256x ≡ 179
256x + 0 ≡ 179 + 337 性質(1)
256x ≡ 516 両辺の計算
64x ≡ 129 性質(5)
64x + 0 ≡ 129 + 337 性質(1)
64x ≡ 466 両辺の計算
32x ≡ 233 性質(5)
32x + 0 ≡ 233 + 337 性質(1)
32x ≡ 570 両辺の計算
16x ≡ 285 性質(5)
16x + 0 ≡ 285 + 337 性質(1)
16x ≡ 622 両辺の計算
8x ≡ 311 性質(5)
8x + 0 ≡ 311 + 337 性質(1)
8x ≡ 648 両辺の計算
x ≡ 81 性質(5)
つまり,x ≡ 81 (mod 337),になります。

(別解)
ちょっと気付かないですが...mod 337 
256x ≡ 179
(337 - 81)x ≡ 179 左辺の計算
337x - 81x ≡ 179 左辺の計算
337x - 81x - 337x ≡ 179 - 0 性質(2)
- 81x ≡ 179 両辺の計算
81x ≡ - 179 性質(3)
81x + 0 ≡ - 179 + 337 * 20 性質(1)
81x ≡ 6561 両辺の計算
81x ≡ 81 * 81 右辺の計算
x ≡ 81 性質(5)
面倒なので,以下では,使った性質に関していちいち示さないことにします。

問題2:
(1) 39x + 47y = 4151
- 8x ≡ 39x ≡ 4151 ≡ 15 (mod 47)
8x ≡ -15 ≡ 32 (mod 47)
x ≡ 4 (mod 47)
そこで,を整数として,
x = 47t + 4y = - 39t + 85

(別解)として,最初に y を求めると,
8y ≡ 47y ≡ 4151 ≡ 17 (mod 39)
8y ≡ 17 ≡ 56 (mod 39)
y ≡ 7 (mod 39)
そこで,を整数として,
x = - 47s + 98y = 39s + 7
になりますが,s = - t + 2 で両者は同じものです。
まぁ,これは当然ですね。

(2) 32x + 57y - 68z = 1
mod 57 で,
32x - 68z ≡ 1
32x ≡ 68z + 1 ≡ 68z + 58
16x ≡ 34z + 29 ≡ 34z + 86
8x ≡ 17z + 43 ≡ 74z + 100
4x ≡ 37z + 50 ≡ 94z + 50
2x ≡ 47z + 25 ≡ 104z + 82
x ≡ 52z + 41
そこで,sを整数として,
x = 57s + 52t + 41z = t
で,は元の式に xを代入して,
32(57s + 52t + 41) + 57y - 68(t) = 1
57y =  - (32 * 57)s - (32 * 52 - 68)t + (1 - 32 * 41)
y = - 32s - 28t - 23
そこで,sを整数として,
x = 57s + 52t + 41y = - 32s - 28t - 23z = t
もちろん,sの自由度で他の表現もあり得ます。

問題3:
(1) 2x + 7y ≡ 1 (mod 13)5x + 10y ≡ 2 (mod 13)
4x + 14y ≡ (2x + 7y) * 2 ≡ 1 * 2 ≡ 2 ≡ 5x + 10y (mod 13)
x ≡ 4y (mod 13)
2x + 7y ≡ 2(4y) + 7y ≡ 15y ≡ 1 (mod 13)
2y ≡ 15y ≡ 1 ≡ 14 (mod 13)
y ≡ 7 (mod 13)
x ≡ 4y ≡ 28 ≡ 2 (mod 13)

(2) x ≡ 3 (mod 5)x ≡ 4 (mod 7)x ≡ 5 (mod 9)
x ≡ 3 (mod 5) より,を整数として x = 5a + 3 です。そこで,
x ≡ 5a + 3 ≡ 4 (mod 7)
5a ≡ 1 ≡ 8 ≡ 15 (mod 7)
a ≡ 3 (mod 7)
つまり,を整数として a = 7b + 3x = 5(7b + 3) + 3 = 35b + 18 です。そこで,
x ≡ 35b + 18 ≡ 5 (mod 9)
35b ≡ - 13 ≡ - 4 ≡ 5 (mod 9)
7b ≡ 1 ≡ 10 ≡ 19 ≡ 28 (mod 9)
b ≡ 4 (mod 9)
つまり,を整数として b = 9c + 4x = 35(9c + 4) + 18 = 315c + 158 になります。

(別解)
7 * 9 ≡ 63 ≡ 3 (mod 5)5 * 9 ≡ 45 ≡ 3 (mod 7)5 * 7 ≡ 35 ≡ 8 (mod 9)
7 * 9 * 2 ≡ 6 ≡ 1 (mod 5)5 * 9 * 5 ≡ 15 ≡ 1 (mod 7)5 * 7 * 8 ≡ 64 ≡ 1 (mod 9)
なので,
x ≡ 7 * 9 * 2 * 3 + 5 * 9 * 5 * 4 + 5 * 7 * 8 * 5 (mod 5 * 7 * 9)
x ≡ 378 + 900 + 1400 ≡ 2678 ≡ 158 (mod 315)
これは,いわゆる中国人の剰余の定理ですね。


*熟読玩味ぃ~♪
...こりゃなれないと難しいですねぇ...^^;
関連記事
スポンサーサイト



コメント

No title

スモークマン

解答をアップさせていただきました♪
非公開コメント

トラックバック