1. 欧拉函数
定义欧拉函数 (oldsymbol varphi(n)) 为 ([1,n]) 中，与 (n) 互质的数的个数。
(2 mid oldsymbol varphi(n)) 当且仅当 (n=1vee n=2)
证明：
根据欧拉函数的积性，对于 (displaystyle n=prod_{i=1}^m p_i^{e_i}Rightarrow oldsymbol varphi(n)=prod_{i=1}^m p_i^{e_i-1}(p_i-1))
当 (n=1) 时，(oldsymbol varphi(1)=1)
当 (n) 含有任意非 (2) 质因数 (p) 时，一定有 (2 mid p) ，因此 (2mid (p-1)) ，故 (2mid oldsymbol varphi(n))
当 (n) 仅含有质因数 (2) 时， (oldsymbol varphi(n)=oldsymbol varphi(2^k)=2^{k-1}Rightarrow [2 mid oldsymbol varphi(n)]=[2 mid 2^{k-1}]=[k=1])
推论：
当 (n eq 1,2,3,4,6) 时，(oldsymbol varphi(n)) 为合数
证明：
(oldsymbol varphi(1)=oldsymbol varphi(2)=1)
(oldsymbol varphi(3)=oldsymbol varphi(4)=2)
(oldsymbol varphi(6)=3)
(oldsymbol varphi(5)=4) 属于合数
根据递推式 (oldsymbol varphi(pcdot n)= egin{cases} (p-1)cdot oldsymbol varphi(n),p mid n \ \ pcdot oldsymbol varphi(n),pmid n end{cases})
当 (n>2,pmid n) 时，(oldsymbol varphi(pcdot n)=pcdot varphi(n)) 必为合数
当 (n=2,pmid n) 时，(p=2Rightarrow pcdot n=2cdot 2=4<6)
当 (n=1vee n=2) 时，对于 (forall p>6,oldsymbol varphi(pcdot n)=(p-1)cdot 1=2cdot {p-1over 2}geq 2cdot {7-1over 2}=2cdot 3) 必为合数
当 (n>2) 时，对于 (forall p mid n)
若 (p>2) 则 (oldsymbol varphi(pcdot n)=(p-1)cdot oldsymbol varphi(n)) 必为合数
若 (p=2) 则 (n>3) 时 (oldsymbol varphi(pcdot n)=oldsymbol varphi(n)) 必为合数
故对于 (forall n>6,oldsymbol varphi(n)) 为合数
综上，当 (n eq 1,2,3,4,6) 时 (oldsymbol varphi(n)) 为合数
2. 莫比乌斯函数
对于 (forall n) ，若 (exist p ext{ s.t. }p^2mid n) 则 (2mid oldsymbol mu(n)) ；否则 (2 mid oldsymbolmu(n))
证明：
当且仅当 (exist p ext{ s.t. }p^2mid n) 时，(oldsymbol mu(n)=0) ，此时为偶数；否则 (oldsymbol mu(n)=pm 1) ，为奇数
3. 组合数
定义 (left( egin{matrix} n \ m end{matrix} ight)) 为 (n) 个数中选 (m) 个的方案数。
当且仅当 (msubseteq n) （即 (n&m=m) ）时为奇数，否则为偶数。
证明：
显然可知 (left( egin{matrix} 0 \ 0 end{matrix} ight)=1, left( egin{matrix} 0 \ 1 end{matrix} ight)=0, left( egin{matrix} 1 \ 0 end{matrix} ight)=1, left( egin{matrix} 1 \ 1 end{matrix} ight)=1)
根据卢卡斯定理，对于 (forall p,left( egin{matrix} n \ m end{matrix} ight)mod p= left( egin{matrix} n/p \ m/p end{matrix} ight)cdot left( egin{matrix} nmod p \ mmod p end{matrix} ight)mod p)
故 (left( egin{matrix} n \ m end{matrix} ight)mod 2= left( egin{matrix} n/2 \ m/2 end{matrix} ight)cdot left( egin{matrix} nmod 2 \ mmod 2 end{matrix} ight)mod 2)
要使得该组合数为奇数，则前后两项均应同余 (1) ；由于 (nmod 2,mmod 2in[0,1]) ，根据上面的等式，需满足：(nmod 2 eq 0vee mmod 2 eq 1)
若将 (0,1) 分别视为某一元集 ({a}) 不选择元素 (a) 与选择元素 (a) 构成的集合 (varnothing,{a}) 则 (nmod 2 eq varnothing vee mmod 2 eq {a})
等价于 ((mmod 2)subseteq(nmod 2))
由于 (nmod 2,mmod 2) 等价于 (n,m) 的二进制第 (0) 位，故记为 (m_0subseteq n_0)
递归考虑 (left( egin{matrix} n/2 \ m/2 end{matrix} ight)) ，其等效于考虑 (n,m) 各右移一位产生的新二进制数 (n',m') 意义下的组合数 (left( egin{matrix} n' \ m' end{matrix} ight))
递归考虑下去，等价于 (m_1subseteq n_1,m_2subseteq n_2,cdots)
即 (msubseteq n)
根据 (msubseteq nLeftrightarrow mcap n=m)
故当且仅当 (m&n=m) 时，组合数 (left( egin{matrix} n \ m end{matrix} ight)) 为奇数
推论：
(displaystyle sum_{i=0}^n [2 mid left( egin{matrix} n \ i end{matrix} ight)]=2^{|n|}) 。其中，(|n|) 表示 (n) 在二进制意义下 (1) 的个数。
(displaystyle sum_{i=0}^n [2 mid left( egin{matrix} n \ i end{matrix} ight)]=sum_{i=0}^n [isubseteq n])
设 (n) 二进制意义下为 (l) 位，则考虑 (l) 元集 ({a_0,a_1,a_2,cdots,a_{l-1}}) 作为全集 (E)
(n) 表示二进制对应 (1) 位选，其余位不选的 (E) 的 (|n|) 元子集
故 (forall isubseteq n,isubseteq E) ，而 (n) 的子集个数 (|P(n)|=2^{|n|})
因此 (displaystyle sum_{i=0}^n [isubseteq n]=2^{|n|})