写一个求解ax同余bmodp求x的算法

求解ax同余b mod p求x的算法可以使用扩展欧几里得算法，具体步骤如下：

1. 首先判断a和p是否互质（即它们的最大公因数是否为1）。如果不互质，则方程无解。

2. 如果a和p互质，则使用扩展欧几里得算法求解ax + py = 1中的解x和y。

3. 对方程两边同时乘以b，得到abx同余b mod p。

4. 将b除以p得到b = kp + r，其中0 <= r < p。

5. 将方程abx同余b mod p代入，得到arx同余r mod p。

6. 将r乘以x的逆元（即x关于模p的乘法逆元，可以使用欧拉定理求解），得到r * x^(-1)同余r * x^(-1) mod p。

7. 两边同时乘以a/x，得到ar/x同余r * a * x^(-1) mod p。

8. 由于a和p互质，所以a关于模p的乘法逆元存在，可以使用欧拉定理求解。将r * a * x^(-1)乘以a关于模p的乘法逆元得到r * a * x^(-1) * a^(-1)同余r * x^(-1) * a^(-1) mod p。

9. 得到x = r * a^(-1) * x^(-1) mod p，即为方程ax同余b mod p的解。

注意：当p为质数时，a关于模p的乘法逆元可以使用费马小定理求解。当p不为质数时，可以使用扩展欧几里得算法求解。