[left( prod_{gcd(i,n)=1}^{n}i
ight) mod n
]
结论：该式子结果为 (1) 或 (-1)。
简单证法
打表可得。（逃）先特殊讨论 (1,2) 都成立。
不难发现这些数都有逆元，如果满足 (p otequiv p^{-1} pmod n)，那么它们两两相乘最后得到的结果就是 (1)。
如果不幸地 (p^2equiv1 pmod n)，那么有 ((n-p)^2=n^2-2np+p^2 equiv 1 pmod n)，所以依然可以两两配对，乘积为 (-1)。
唯一特殊情况为 (2p=n)，此时 (gcd(2p,n)=p)，故此数字不会被计入答案。
例题 CF1514C
题意：从 (1,2,cdots,n-1) 中选尽可能多的数出来，使得其乘积模 (n) 为 (1)。
题解：首先肯定不能选不互质的数，然后就转化为上述问题。根据乘积为 (1) 或 (-1) 决定是否去除 (n-1)。