こんにちは。R86plusAブログの時空です。今回は前回の素因数分解を解いてみたという記事で誤りがあったのでもう一度書き直した記事を上げたいと思います。
まず、3511×1429=5017219の素因数分解についてです。
5017219=79mod108, 5017219=58mod109, 5017219=103mod116,
79mod108-58mod109=a
(5017219-108×1429)-(5017219-109×1429) = 4862887-4861458 = 1429
58mod109-103mod116=7a
(5017219-109×1429)-(5017219-116×1429) = 4861458-4851455=1429×7
第１式の右辺aを第２式の右辺7aに代入する。
58mod109-103mod116=7x(79mod108-58mod109)
4862887×7-4861458×7
(8×58)mod109=103mod116+(7×79)mod108
38891664
28mod109 = 103mod116+13mod108
38891664 = 4851455 + 4862887×7
28mod109 = 88mod224
38891664 = 38891664
ここから先は自分で考えてみよう！
28+109p = 88+224qでもいい。
79mod108=5017219-108a=79+108s+108aというような変形も可能だ。極端な話。79mod108=5017219と置き換えてもいい。僕ももう少し考えてみるので面白い提案があれば、コメントに一筆ください。ではでは。
(補足) 28 mod 109 = 88 mod 224は何を意味するのか。28 mod 109は(58mod109)x8である。一方、88mod224もx8されたものだが、x8される前の数値に戻してみると(88mod224)/8=11mod28となり、偶然かどうかは分からないけど、3511=11mod28と同じであることが分かる。今回の課題は3511×1429の素因数分解なのでこれが正解かは他のサンプルでチェックしてみてください。
コメント