应该可以证明N=φ(n)对任意正奇数n都成立, 这样当n是奇合数时N≤n-2都成立
用归纳法可以证明对奇素数p和正整数k, 对模p-1的每个给定剩余类r(mod p-1), 都恰好有一个模p^k的剩余类 l(mod p^k), 使得当正整数x≡r(mod p-1),x≡l(mod p^k)时2^x≡x(mod p^k)
所以2^x≡x(mod p^k)正好有p-1个模(p-1)p^k的不同解, 而且对满足p-1|n, (p,n)=1的正整数n, 对给定的模n剩余类r(mod n), 都恰好只存在一个模p^k的剩余类 l(mod p^k), 使得当正整数x≡r(mod n), x≡l(mod p^k)时2^x≡x(mod p^k)

然后假设n是使得N≠φ(n)的最小正奇数, 则n>1, 设n的最大素因子是p, 正整数k,m满足n=m*p^k, 则mφ(m)的最大素因子小于p, 与p互素
因为2^x≡x(mod n)当且仅当2^x≡x(mod m)且2^x≡x(mod p^k),
由于n是不符合结论的最小正整数, m<n, 所以2^x≡x(mod m)的解是φ(m)个不同的模mφ(m)的剩余类, 可以看作(p-1)φ(m)个模(p-1)mφ(m)的剩余类
对其中每个剩余类r(mod (p-1)mφ(m)), 按照之前的结论都只存在唯一一个模p^k的剩余类l(mod p^k), 使得当正整数x≡r(mod (p-1)mφ(m)), x≡l(mod p^k)时 2^x≡x(mod p^k)成立, 则2^x≡x(mod n)也成立
这说明2^x≡x(mod n)的解应该是(p-1)φ(m)个模(p-1)p^k*mφ(m)的剩余类, 对应着φ(p^k)*φ(m)个模φ(p^k)p^k*mφ(m)的剩余类, 也就是φ(n)个模nφ(n)不同的剩余类, 与结论不成立的假设矛盾, 所以对任意正奇数n, N=φ(n)都成立