コンピュータに頼りたくない。
通常の電卓ぐらいで次の合同式は解けますか？
(1)1234*x^567≡89 (mod 101)
(2)98*x^76543≡21 (mod 101)
全部手計算で電卓も使いませんでした。
(mod 101)は省略します。
(1)
x≡0は解にならないのでx^100≡1
また1234≡22なので1234*x^567≡22*x^67
22y≡89とすると
22y-101n=89
22(y-4)-101n=1
22(y-4-5n)+9n=1
9{2(y-4-5n)+n}+4(y-4-5n)=1
9(2y-8-9n)+4(y-4-5n)=1
2y-8-9n=1,y-4-5n=-2を解くとy=27,n=5
よって22y≡89の解はy≡27なので
x^67≡27を解けばよい。
x^201≡27^3=19683≡89
∴x≡89
(2)
x≡0は解にならないのでx^100≡1
また98≡-3なので98*x^76543≡-3*x^43
3*x^43≡-21
x^43≡-7
x^301≡(-7)^7=-343*2401≡-40*78≡-3120≡-90≡11
∴x≡11
