potetoichiro: この世の終わりのような約分
どうやって思いつくのかという話があったので解説を書く
- aの桁数をNとする
- なので分母を払って である
- aについて整理すると
- 以降簡単のためにと書く
- 任意の数で余りをとっても等式が成立するので十分大きな素数Pで割る
- この時、aは
- フェルマーの小定理で
- よって を決めれば が決まる
- 正しく求まってるか確認する(Nが求めたaの長さに一致しないことがほとんど)
- Pを複数個用意すると中国剰余定理を使って大きなaを求めることもできる
Tweetまとめ
nishio: どうやって思いつくのかという話があったけど(10a+b)/(c×10^len(a)+a)=b/cなので(10a+b)c=(c×10^len(a)+a)bで、全部整数なので任意の数で余りをとっても等式が成立するので以下略(スマホで数式描くのつらすぎ nishio: b,cが互いに素である場合、こんな感じでaはbcの倍数であることがわかる、後は最後の式だがaとbcが素でないので逆元がどうなるかというと…
nishio: 僕が続きを計算してる間に元のでかい分数で上記の等式が成立するのを確かめててください
- 712158808933002481389578163771 mod 7 * 41
nishio: あれー、なんか他に条件がいるかな、これだけだと正解以外にたくさん解がでてしまう nishio: わからなくなったので一旦白旗
nishio: 12_307692 / 307692_3 = 4 41_302211 / 302211_3 = 41 / 3 57_301587 / 301587_3 = 19 71_301272984441 / 301272984441_3 = 71/3
nishio: そうか[中国剰余定理]だ！と思いついて、式をaについて整理してから10^9程度の十分大きな素数二つで剰余をとってCRTしたけど、結局のところ10^9より小さい解もあったので本質はCRTではなく、十分大きな素数を持ってくればフェルマーの小定理で逆元が求まるところですね
nishio: いまこういう自明なやつを取り除いて一覧を出す準備をしてます 5050505050505050_5 / 50_5050505050505050 = 1/10
nishio: bが1桁、cが最大2桁の範囲で10倍のやつを除いて297個ありますね。この列挙に0.2秒でした。 https://gist.github.com/nishio/488da0129efec7f9940bd4a521fb91b7
nishio: あ、書き忘れたけどaの桁数は2〜17にしました。出力を見ればわかるように桁数を制限しないと無数にあります。
source code: https://gist.github.com/nishio/0a281988f2a9ddb37259e8a23fcf3316
関連
dorako220: レピュニット数の素因数分解の一覧を使えば結構簡単に作れます pic.twitter.com/EDWhnmmx1l