{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 jnjavelin 的文章《模线性方程（和一个数的逆）》','https://www.xiaopingtou.net/article-51749.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
描述：
输入正整数a,b,n,解方程
。
。(
表示的含义是“a和b关于模n的同余”，即
）
分析：
原方程可理解成ax-b=ny,移项得ax-ny=b;然后就可以用扩展欧几里得
这里有个特殊情况需指出，b=1时，
的解称为a关于模n的逆（inverse），它类似于实数运算中的倒数的概念。
那么什么时候a的逆存在呢？即方程ax-ny=1要有解，这样1必须是gcd（a,n）的倍数，因此a和n必须互素（即gcd(a,n）=1),所以若a，n互素，
只有唯一解
。。(表示的含义是“a和b关于模n的同余”，即）
分析：
原方程可理解成ax-b=ny,移项得ax-ny=b;然后就可以用扩展欧几里得
这里有个特殊情况需指出，b=1时，的解称为a关于模n的逆（inverse），它类似于实数运算中的倒数的概念。
那么什么时候a的逆存在呢？即方程ax-ny=1要有解，这样1必须是gcd（a,n）的倍数，因此a和n必须互素（即gcd(a,n）=1),所以若a，n互素，只有唯一解