如果 $\gcd(x,y)\neq 1,\gcd(k,y)\neq 1$ 那么 $\gcd(kx,y)\neq 1$，于是 $\gcd(k^l,y)\neq 1$，于是显然无解
by qwaszx @ 2020-07-01 15:22:24
@[qwaszx](/user/22136) 懂了，谢谢Thanks♪(･ω･)ﾉ
by 辰星凌 @ 2020-07-01 15:36:21
题解里貌似没有提到...在这里补充一下完整证明吧。
**【结论】**
$\exists x\in N^{*},a^x=1(\bmod m)$ $\iff$ $\gcd(a,m)=1$
**【证明】**
> 右推左证明：
由欧拉定理可知当 $x=\varphi(m)$ 时该同余方程成立。
证毕。
> 左推右证明：
易知 $\exists x\in N^{*},\gcd(a^x,m)=\gcd(a^x,a^x\mod m)=\gcd(a^x,1)=1$
假设 $\gcd(a,m)\neq1$，则 $\forall k\in N^{*}, \gcd(a^k,m)\neq1$
所以 $\forall k\in N^{*}, \gcd(a^k,a^k\mod m)\neq 1$，与前者 $\exists x\in N^{*},\gcd(a^x,m)=1$ 矛盾
所以必有 $\gcd(a,m)=1$
证毕。
by 辰星凌 @ 2020-07-01 16:05:07
```cpp
题解里貌似没有提到...在这里补充一下完整证明吧。
**【结论】**
$\exists x\in N^{*},a^x=1(\bmod m)$ $\iff$ $\gcd(a,m)=1$
**【证明】**
> 右推左证明：
由欧拉定理可知当 $x=\varphi(m)$ 时该同余方程成立。
证毕。
> 左推右证明：
易知 $\exists x\in N^{*},\gcd(a^x,m)=\gcd(a^x,a^x\mod m)=\gcd(a^x,1)=1$
假设 $\gcd(a,m)\neq1$，则 $\forall k\in N^{*}, \gcd(a^k,m)\neq1$
所以 $\forall k\in N^{*}, \gcd(a^k,a^k\mod m)\neq 1$，与前者 $\exists x\in N^{*},\gcd(a^x,m)=1$ 矛盾
所以必有 $\gcd(a,m)=1$
证毕。
```
by 辰星凌 @ 2020-07-01 16:05:19
@[辰星凌](/user/110985) u1s1 这可能太显然了(
by qwaszx @ 2020-07-01 16:08:23
@[qwaszx](/user/22136) 主要是我太菜了不能一眼看出来
by 辰星凌 @ 2020-07-01 16:14:24
打破红名金钩队形（逃
by Terryhalk_chester @ 2021-03-07 15:26:37