• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【数论】线性模方程

admin

11月 28, 2021

求方程ax=c(mod b)的解

可将其转换为 ax+by=c

有解条件:(a,b)|c

设k*(a,b)=c

用拓展欧几里得求出方程ax+by=(a,b)的解(x,y)

x’=k*x,y’=k*y 就是方程的一个解

所以x’+i*(b/(a,b)) (i=0,1,2,..,(a,b)-1) 是原方程的解

证明:

设sx[i]=x’+i*(b/(a,b)),sy[i]=y’-i*(a/(a,b))

则需证明a*sx[i]+b*sy[i]=c

a*sx[i]+b*sy[i]

=a*(x’+i*(b/(a,b)))+b*(y’-i*(a/(a,b)))

=ax’+by’+a*i*b/(a,b)-b*i*a/(a,b)

=ax’+by’

=c 得证

发表回复

您的电子邮箱地址不会被公开。