关于F唯一性的另一种证明方式
奇素数回路
https://ac.nowcoder.com/acm/contest/109081/F
证明： 若，
，序列
包含 n 个从 1 到 n 的不同整数，
等效于：若p与n互质，则在时，
不同时
的值也不同。
我们可以使用反证法+裴署定理证明
因为 ，所以存在整数
和
使得
（裴署定理）。
显然，两边模 ，知
，即
是
的乘法逆元。
这里使用反证法：
如果且
，我们可以两边乘以
（
的逆元）：
因为 ，所以
，矛盾。
故得证。
腾讯公司福利 832人发布
投递腾讯等公司6个岗位 >
