n,mn,mn,m を異なる非負整数とし、k=ν2(n−m)k=\nu_2(n-m)k=ν2(n−m) と置く。k 未満の2進桁は一致し、k 桁目は異なる。n−mn-mn−m は 2k2^k2k の非零倍なので ∣n−m∣≥2k|n-m|\ge2^k∣n−m∣≥2k。一方が0でも同じである。 kkk kkk ν2(n−m)\nu_2(n-m)ν2(n−m)