$p$ 对 $1\dots n$ 互质就行？
by RenaMoe @ 2022-06-14 18:37:45
@[RenaMoe](/user/52243) 这个和p是质数一个意思吧？
by 忘怀星 @ 2022-06-14 18:50:26
@[RenaMoe](/user/52243) 我也是这么认为的，但这篇日报 [link](https://www.zhihu.com/tardis/sogou/art/86561431) 上提到了 p 必须是一个素数的要求
by VectorLi @ 2022-06-14 18:51:42
@[忘怀星](/user/305911) 但如果 p 不是一个素数，n 又小于 p 的最小质因子呢
by VectorLi @ 2022-06-14 18:53:00
@[忘怀星](/user/305911) $p$ 是两个 $>n$ 的质数的乘积感觉也行
by RenaMoe @ 2022-06-14 18:54:13
@[VecTest](/user/609972) exgcd 可以吧
by Fast_IO @ 2022-06-14 18:55:03
@[Fast_IO](/user/229366) exgcd 可以，但我不确定线性递推是否可以
by VectorLi @ 2022-06-14 18:56:10
当 $n<p$ 的最小质因子时即可
by Jasper08 @ 2022-06-14 18:56:38
@[Jasper08](/user/581830) 请问可以证明一下吗
by VectorLi @ 2022-06-14 18:58:13
@[Jasper08](/user/581830) 就是为什么不需要 p 是一个素数
by VectorLi @ 2022-06-14 18:59:26