E-Throne ～合同方程式(ax≡b (mod m))とgcdの関係をつかむ動画2つ～

• https://atcoder.jp/contests/abc186/tasks/abc186_e
• editorialを見ると、合同式の方程式を解く方法が知りたくなる。例えば

ax ≡ b (mod m)

これを満たすxを求めたいが、xは存在することもあるし、存在しないこともある
gcd(a, m)の値が重要になる
高校の数Aで学ぶ

• 数Aを読み直すかーと思っていたが、現状は以下の動画で間に合った

動画2つ

• kogaさん
• ユークリッドの互除法と一次不定方程式【合同式とRSA暗号：第4回】https://www.youtube.com/watch?v=2t8UepAuWcM
• 合同式の重要性質２（乗法単元）【合同式とRSA暗号：第5回】https://www.youtube.com/watch?v=ZSrPQbh7ENg
• この2つは見て損はない