2021年中国台湾IMOC——数论组

每年，我国台湾的前IMO参赛者组成的小团体都会举办一个夏令营，讲解知识和技巧，还有8次模拟考试．从2017年开始，他们取消了模拟考试，用若干练习题来取代．下面就是2021年中国夏令营的IMOC练习题．

数论组

1. (LTE引理)证明以下四个结论：
   (1)对任意非零整数𝑚，𝑛和质数𝑝，都有𝑣_(𝑝)(𝑚𝑛)=𝑣_(𝑝)(𝑚)+𝑣_(𝑝)(𝑛)；
   (2)如果奇质数𝑝，正整数𝑘，整数𝑎和𝑏满足：𝑝∤𝑎，𝑝∤𝑏，𝑝∣𝑎−𝑏，𝑝∤𝑘，则𝑣_(𝑝)(𝑎^(𝑘)−𝑏^(𝑘))=𝑣_(𝑝)(𝑎−𝑏)；
   (3)如果奇质数𝑝满足：𝑝∤𝑎，𝑝∤𝑏，𝑝∣𝑎−𝑏，则𝑣_(𝑝)(𝑎^(𝑝)−𝑏^(𝑝))=𝑣_(𝑝)(𝑎−𝑏)+1；
   (4)如果奇质数𝑝，正整数𝑘，整数𝑎和𝑏满足：𝑝∤𝑎，𝑝∤𝑏，𝑝∣𝑎−𝑏，则公式：v_{p}(a^{k}-b^{k})=v_{p}(a-b)+v_{p}(k)．
2. 求证：对任意两个不同的奇质数𝑝和𝑞，存在一个正整数𝑛，满足{𝑑(𝑛),𝑑(𝑛+2)}={𝑝,𝑞}，其中𝑑(𝑛)表示𝑛的最小质因子．
3. 定义函数𝑓:ℕ_(>1)→ℕ_(>1)满足𝑓(𝑥)为𝑥的最大质因子．正整数数列{𝑎_(𝑛)}满足𝑎_(1)=𝑀>1，且

公式：a_{n}=\left\{ \begin{array}{ll} a_{n}-f(a_{n}),&a_{n}\text{为合数}\\ a_{n}+k,&\text{其余情况} \end{array} \right.

求证：对任意正整数𝑀和𝑘，数列{𝑎_(𝑛)}有界．

4. 𝑚≥3个正整数（不必互异）排列在一个圆周上，满足每个正整数均整除它两边的两个正整数之和．求证：如果这些数中恰有一个1，则对任意正整数𝑛，至多有𝜑(𝑛)个𝑛．
5. 求满足下述所有条件的正整数集合𝑆：
   (1)若𝑎和𝑏均在𝑆中（𝑎，𝑏不必互异），则gcd(𝑎,𝑏)也在𝑆中；
   (2)若正整数𝑚和𝑛满足𝑛∤𝑚，则𝑆中存在元素𝑠满足𝑚^(2)∣𝑠，𝑛^(2)∤𝑠；
   (3)对任意奇质数𝑝，集合𝑆中的元素按照模𝑝的余数恰好能分成(𝑝+1)/(2)类．
6. 求证：不存在正整数𝑥，𝑦，𝑧满足𝑥^(𝑥)+𝑦^(𝑦)=9^(𝑧)．
7. 给定奇质数𝑝．求最大的正整数𝑘^(′)，使得能将集合{1,2,⋯,𝑝−1}分成两个集合𝑋和𝑌，满足对任意从0到𝑘^(′)的整数𝑘，都有

   公式：\sum\limits_{a\in X}a^{k}\equiv \sum\limits_{b\in Y}b^{k}({\rm{mod}}\ p)\text{．}
8. 求所有整值多项式𝑓，𝑔：ℕ→ℕ，使得∀𝑥∈ℕ，𝜏(𝑓(𝑥))=𝑔(𝑥)均成立，其中𝜏(𝑥)表示𝑥的正约数个数．
9. 求所有正整数对(𝑎,𝑏)，使得存在无穷整数集合𝑆，任意正整数𝑛均能表示为

   𝑛=𝑥^(𝑎)+𝑦^(𝑏)+𝑠

   的形式，其中𝑥和𝑦为非负整数，𝑠为𝑆中的元素．
10. 称一个质数𝑝为“完美的”，如果存在1，2，⋯，𝑝−1的一个排列：𝑎_(1)，𝑎_(2)，⋯，𝑎_((𝑝−1)/(2))，𝑏_(1)，𝑏_(2)，⋯，𝑏_((𝑝−1)/(2))满足对∀1≤𝑖≤(𝑝−1)/(2)，有𝑎_(𝑖)+𝑎−1𝑖≡𝑏_(𝑖)(mod𝑝)．求证：存在无穷多个不完美的质数．
11. 给定一个奇质数𝑝．映射𝜎：{1,⋯,𝑝−1}→{1,⋯,𝑝−1}满足𝑖⋅𝜎(𝑖)≡1(mod𝑝)对任意𝑖∈{1,⋯,𝑝−1}均成立．求证：满足𝑎<𝑏且𝜎(𝑎)>𝜎(𝑏)的数对(𝑎,𝑏)∈{1,⋯,𝑝−1}^(2)的个数至少为

    ⌊((𝑝−1)/(4))^(2)⌋．

    
    注：如果将结论中的4换成更大的常数，则可能会得到部分分数．