部落格

此文章來自奇摩知識+如有不便請留言告知

標題:

同餘方程一

發問:

解同餘方程： 1. 68^120 ≡ x (mod 2013) 2. 68^101 ≡ x (mod 2013) 3. 1001^1003 ≡ x (mod 2013) 4. 12x ≡ 18 (mod 42)

最佳解答:

1) 6812o ≡ (68^5)^24 ≡ (- 32)^24 ≡ 212o ≡ (211)1o * 21o ≡ 351o * 1024 ≡ 51o * 71o * 1024 ≡ 562 * 1024 * 1024 ≡ 1 = x (mod 2013) 2) 681o1 ≡ (68^5)2o * 68 ≡ (- 32)2o * 68 ≡ 21oo * 68 ≡ (211)^9 * 2 * 68 ≡ 35^9 * 136 ≡ 6023 * 136 ≡ 281 * 136 ≡ 1982 = x (mod 2013) 3) 10011oo3 ≡ 911oo3 * 111oo3 ≡ (91^4)^250 * 913 * (11^5)2oo * 113 ≡ 103^250 * 913 * 112oo * 113 ≡ 103^250 * 913 * ((11^5)^5)^8 * 113 ≡ (103^4)^62 * 1032 * 913 * 11^8 * 113 ≡ 25^62 * 1032 * 913 * 11^5 * 11^5 * 11 ≡ (25^6)1o * 252 * 1032 * 913 * 11 * 11 * 11 ≡ (- 41)1o * 252 * 1032 * 913 * 11 * 11 * 11 ≡ (41^5)2 * 252 * 1032 * 913 * 11 * 11 * 11 ≡ (- 1)2 * 252 * 1032 * 913 * 11 * 11 * 11 ≡ 25752 * 10013 ≡ - 197 * - 418 ≡ 82346 ≡ 1826 = x (mod 2013) 4) 12x ≡ 18 (mod 42)故 2x ≡ 3 (mod 7) ... (1) 又 7x ≡ 0 (mod 7) ... (2)(1)*4 - (2) : 8x - 7x ≡ 12 - 0 (mod 7) x ≡ 12 (mod 7) x ≡ 5 (mod 7)

其他解答:A9A3995996B435E3