how to

中国剩余定理

Oct 9, 2024
notesjulyfun数学基础数论
1 Minutes
95 Words

题目:求 𝑥 满足以下,其中 𝑛𝑖 两两互质

{{{{{{{𝑥mod𝑛1=𝑎1𝑥mod𝑛2=𝑎2𝑥mod𝑛𝑘=𝑎𝑘

求解:

  • 计算模数的积 𝑛
  • 对第 i 个方程
    • 𝑚𝑖=𝑛𝑛𝑖
    • 𝑚1𝑖𝑚𝑖 在模 𝑛𝑖 下的逆元
    • 𝑐𝑖=𝑚𝑖𝑚1𝑖,不要模 𝑛𝑖
  • 𝑛 意义下 𝑥 唯一解为 𝑘𝑖=1𝑎𝑖𝑐𝑖 . 正确性比较显然
Article title:中国剩余定理
Article author:Julyfun
Release time:Oct 9, 2024
Copyright 2025
Sitemap