（a=bc mod d） 那么c=？

Question

（a=bc mod d） 那么c=？
a和b都是已知值，d是一个固定常数，满足d=（p-1）*（q-1），p和q都是质数，且c与d互质，问c怎么求？打个比如，d=103002120 （p=10159 q=10141 ）
a=44 143 785 b=44 908 502 题目只有答案没过程（感觉我买了假的暑假作业），怎么求得c=7？
还有m|b表示什么意思，中间的|号什么意思？（怪我上课睡觉咯。。听老师讲过，当时没留意，貌似是取模计算那章的课程）
写错了，条件1，a=135 b=44 143 785 d=103002120
条件2，a=5 353 154 b=44 908 502 d=103002120
2个条件，只能取一个来算、怎么算出c=7，

Answer 1

模，外语mod的音译，就是求余数。
a=bc mod d，a等于bc除以d的余数。

bc=kd+a，
c=（kd+a）/b
k为整数，0≤a≤d-1追问

那么大的范围，怎么能根据1个已知数，a=135 b=44 143 785 d=103002120 算出k，c和k都是未知数啊。。。是不是c和k有多个答案。不唯一

追答

对。一般求出的是最小的c值，如果c是一个满足要求的解，则c+nd也是满足要求的解：
a=bc mod d
b（c+nd） mod d
=（bc mod d）+（bnd mod d），
bnd是d的整数倍，后项为0
b（c+nd） mod d
=（bc mod d）
=a

为了明确c，k是变量，用x,y代替
bx-dy=a
一般用辗转相除法求解。

追问

用条件2，a=5 353 154 b=44 908 502 d=103002120 （p=10159 q=10141 ）
算一次c来看看，c要最小值的c

追答

你的数太大，计算器不能精确计算。
我用一个简单例子说明辗转相除法的做法
3x十4y=5
3x十（3十1）y=3十2
3（x十y-1)十y=2
设x1= x十y-1，
3x1十y=2
x1=0,y=2
x=x1十1-y
=0十1-2=-1
3×（-1）十4×2=5