別急
慢慢做
上次分享了一波數競幾何題（傳送門），然後有模友表示不過癮（估計失眠有點嚴重），想再來一波數論的。。。
既然這樣，那在這美好的週末，超模君特此奉上12道來自單墫教授主編的奧數書——《初等數論》裡面的精彩數論題，請模友們過目！
01
問題：
找出所有使得 2n – 1 能被 7 整除的正整數 n 。
答案：
由於 2n 的二進制表達為 1000…00 （n 個 0），因此 2n – 1 的二進制表達為 111…11 （n 個 1）。
而 7 的二進制表達是 111 ，要想讓它整除 n 個 1 ，顯然 n 必須是也只能是 3 的倍數。
02
問題：
是否存在 100 個數，使得它們的和等於它們的最小公倍數？
答案：是的。
考慮 3, 2 × 3, 2 × 32 , 2 × 33, …, 2 × 398, 399 ，它們的和為：
3 + 2 × 3 + 2 × 32 + 2 × 33 + … + 2 × 398 + 399
= 3 × (1 + 2) + 2 × 32 + 2 × 33 + … + 2 × 398 + 399
= 32 + 2 × 32 + 2 × 33 + … + 2 × 398 + 399
= 32 × (1 + 2) + 2 × 33 + … + 2 × 398 + 399
= 33 + 2 × 33 + … + 2 × 398 + 399
= … …
= 399 + 399
= 2 × 399
而這 100 個數的最小公倍數正是 2 × 399 。
03
問題：
能否找出 100 個不同的正整數，使得其中任意 2 ≤ k ≤ 100 個數的算術平均數都恰為整數。
答案：能。
這個問題非常唬人，它的答案異常簡單： 1 · 100!， 2 · 100!， 3 · 100!， …， 100 · 100! 顯然滿足要求。
04
問題：
求證，存在任意長的連續正整數，使得其中任何一個數都不是質數的冪（當然更不能是質數）。
答案：
有一個經典的問題是，求證存在任意長的連續正整數，它裡面不包含任何質數。
換句話說，相鄰質數的間隔可以達到任意大。構造的方法堪稱經典。
顯然 n! + 2 是 2 的倍數（因為我們可以提出一個 2 來）， n! + 3 是 3 的倍數，等等。
因此， n! + 2, n! + 3, n! + 4, …, n! + n 就是 n – 1 個連續的正整數，其中任意一個數都不是質數。由於 n 可以任意大，因此這個數列可以任意長。
現在，我們要證明的是一個更強的結論。我們可以把剛才的構造方案簡單地修改一下。
只需要考慮 (n!)² + 2，(n!)² + 3，(n!)² + 4， …， (n!)² + n ，則其中每一個數都不是質數的冪。
比如說 (n!)²+ 5 ，顯然它是 5 的倍數，因為我們可以提出一個 5 來；然而提出一個 5 之後將會得到 5 · (1²· 2² · 3² · 4² · 5 · 6² · … · n² + 1) ，括號裡的數顯然不再是 5 的倍數，它除以 5 餘 1 。
利用中國剩餘定理，我們還能給出另一種非常巧妙的構造方案，它能找出 n 個不含質數冪的連續正整數數列，其中 n 可以任意大。
我們只需要保證，每個數都含有至少兩個不同的質因數即可。
取 2n 個不同的質數 p1, p2, …, pn, q1, q2, …, qn ，顯然 p1 · q1, p2 · q2, …, pn · qn 是兩兩互質的 n 個數。
由中國剩餘定理，我們能找到一個正整數 M ，使得 M 除以 p1 · q1 餘 1 ，並且 M 除以 p2 · q2 餘 2 ，並且 M 除以 p3 · q3 餘 3 ，一直到 M 除以 pn · qn 餘 n 。
於是， M – 1, M – 2, M – 3, …, M – n 就是 n 個連續的正整數，其中每一個都含有兩個不同的質因數。
05
問題：
求證，對於任意大的 n ，我們都能夠找出 n 個兩兩互質的數，使得任意 2 ≤ k ≤ n 個數之和都不是質數
答案：
如果只要求任意多個數之和都不是質數，這很好辦：讓所有數都是某個數的倍數即可。
但是，如果這些數必須兩兩互質，同樣的要求還能辦到嗎？
可以的。
考慮 n! + 1, 2 · (n!) + 1, 3 · (n!) + 1, …, n · (n!) + 1 這 n 個數，顯然任意 k 個數之和都是 k 的倍數，因而不是質數。
下面說明這 n 個數兩兩互質。假設 i · (n!) + 1 和 j · (n!) + 1 有公共的質因數 p ，其中 1 ≤ i < j ≤ n ，那麼它們的差 (j - i) · (n!) 也能被 p 整除，說明 p 只能是不超過 n 的質數。這與 p 能整除 i · (n!) + 1 矛盾。
06
問題：
證明，對於任意正整數 n ，方程 x² + y² = zⁿ 都有無窮多組正整數解。
答案：
考慮 x + yi = (a + bi)ⁿ ，其中 i 為虛數單位。
對於每一個固定的 n ，只要 a 和 b 都是整數，那麼展開後得到的 x 和 y 也都一定是整數。
我們選取充分大的 a ，讓 a + bi 的輻角非常小非常小（小於 π/2 的 n 分之一），從而讓 (a + bi)ⁿ 不會與座標軸重合，因而保證 x 和 y 都是非零整數。
等式兩邊同時取模，便有 x² + y² = (a² + b²)ⁿ
07
問題：
我們把平面直角座標系上所有橫縱座標互質的整格點（也就是和原點的連線不經過其他點的整格點）叫做“既約格點”。
證明，對於任意大的正整數 n ，總存在一個整格點，它到任意既約格點的距離都大於 n （換句話說，既約格點集的“空洞”可以達到任意大）。
答案：
列一張 (2n + 1) × (2n + 1) 的表，每個格子裡面填寫一個不同的質數（由於質數無窮多，這是總可以辦到的）。
現在，找出這樣的一個 a ，它除以第 i 行的質數總是餘 i （其中 – n ≤ i ≤ n ）。
找出這樣的一個 b ，它除以第 j 列的質數總是餘 j （其中 -n ≤ j ≤ n）。
中國剩餘定理保證了這樣的 a 和 b 是存在的。
下面說明，點 (a, b) 滿足要求。
假如 (a, b) 到 (x, y) 的距離不超過 n ，則 (a – x)² + (b – y)² ≤ n² 。
因而， a – x 和 b – y 都必須在 – n 到 n 的範圍內。
把 a – x 的值記作 i ，把 b – y 的值記作 j ，那麼 x 就等於 a – i ， y 就等於 b – j ，由 a 、 b 的構造可知， x 和 y 都是表格中第 i 行第 j 列的那個質數的倍數，故 (x, y) 不是既約格點。
08
問題：
找出所有這樣的正整數序列 (a1, a2, …, an) ，它們的和為 2n ，但我們無法把它們分成和相等的兩組。
答案：
考慮 a1, a2, a1 + a2, a1 + a2 + a3, …, a1 + a2 + a3 + … + an ，除了 a1 和 a2 以外，這些數除以 n 的餘數不允許相等，否則它們的差就是 n 的倍數，我們就找到了和為 n 的子集。
然而，上面一共有 n + 1 個數，它們除以 n 的餘數必然有相等的，因而一定是 a1 和 a2 除以 n 的餘數相等。
類似地， a2 和 a3 除以 n 的餘數也相等， a3 和 a4 除以 n 的餘數也相等，因而事實上從 a1 到 an 所有的數除以 n 的餘數都是相等的。
但是這 n 個數加起來只有 2n ，可見所有的數除以 n 的餘數只可能都是 1 或者都是 2 。
於是我們得到了所有滿足要求的數列： (1, 1, 1, …, 1, n + 1) ，以及 (2, 2, 2, …, 2) 。其中後者要求 n 為奇數。
09
問題：
證明，存在無窮多個正整數三元組 (a, b, c) ，使得 a² + b² 、 b² + c²、 a² + c² 都是完全平方數。
答案：
任取一組勾股數 (x, y, z) ，令 a = x|4y2 – z2| ， b = y|4x2 – z2|， c = 4xyz 。於是，
a² + b² = x²(3y² – x²)² + y²(3x² – y²)²
= x6 + 3x²y4 + 3x4y² + y6
=(x² + y²)³ = (z³)²
a² + c² = x²(4y² + z²)²
b² + c² = y²(4x² + z²)²
從而 a 、 b 、 c 滿足要求。由於勾股數有無窮多組，因此滿足要求的 (a, b, c) 也有無窮多組。
這相當於給出了 Euler 磚塊（所有稜長和所有面對角線都是整數的長方體）的一種構造解。
當 (x, y, z) = (3, 4, 5) 時，我們將得到稜長分別為 117 、 44 、 240 的 Euler 磚塊，這就是最小的 Euler 磚塊，它是由 Paul Halcke 在 1719 年發現的。
大家或許會想，有沒有什麼長方體，不但所有稜長和所有面對角線都是整數，連體對角線也是整數呢？
這樣的長方體就叫做完美長方體。
有趣的是，雖然 Euler 磚塊有無窮多種，但是人們目前還沒有找到哪怕一個完美長方體。完美長方體究竟是否存在，目前仍然是一個未解之謎。
10
問題：
證明，若正整數 a 和 b 互質，則 [b / a] + [2b / a] + [3b / a] + … + [(a – 1) b / a] = (a – 1)(b – 1) / 2 。其中， [n] 是 n 的整數部分，即對 n 取下整。
答案：
我們先舉一個例子來說明這個問題的複雜性。
數列 [b / a], [2b / a], [3b / a], …, [(a – 1) b / a] 的規律並不一定非常明確。
例如，當 a = 17 且 b = 12 時， [12 / 17], [2 · 12 / 17], [3 · 12 / 17], … [16 · 12 / 17] 分別為 0, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 11 ，但這 16 個數之和為 88 ，正好是 16 和 11 乘積的一半。
結論的證明很有意思。在平面直角座標系的第一象限擺放一個寬為 a ，高為 b 的矩形。
則 [k · b / a] 就是圖中第 k 條紅色豎直線上的整格點數目，所有 [k · b / a] 之和也就是陰影三角形內的整格點總數。
然而由於 a 和 b 互質，矩形的對角線不會經過矩形內部的任何格點，因此陰影三角形內的整格點數就應該是矩形內的整格點數的一半，即 (a – 1)(b – 1) / 2。
11
問題：
若正無理數 α 和 β 滿足 1 / α + 1 / β = 1 ，求證數列 [1 · α], [2 · α], [3 · α], … 和 [1 · β], [2 · β], [3 · β], … 既無重複又無遺漏地包含了所有的正整數。這裡 [ ] 同樣是取下整的意思。
答案：
讓我們先來看一個例子吧。
考慮黃金比例 φ = (√5 + 1) / 2 ≈ 1.618 ，我們有 1 / φ + 1 / (φ + 1) = 1 。
數列 [1 · φ], [2 · φ], [3 · φ], … 為 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, … ，而數列 [1 · (φ + 1)], [2 · (φ + 1)], [3 · (φ + 1)], … 則為 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, … 。
你會發現，前一個數列裡沒有的數，正好都在後一個數列裡，而後一個數列裡沒有的數，前一個數列里正好都有。
兩個數列合在一起，就是整個正整數序列。
這個定理叫做 Beatty-Rayleigh 定理，它有很多種證明，這裡給出一種我非常喜歡的證明，它出自 Using your Head is Permitted 。
首先注意到，如果 x 和 y 都不是整數，那麼 [x] 嚴格地小於 x ，[y] 嚴格地小於 y ，從而 [x] + [y] < x + y 。
另外，[x] 一定嚴格地大於 x – 1 ， [y] 一定嚴格地大於 y – 1 ，從而 [x] + [y] 一定嚴格地大於 x + y – 2。
這說明，當 x 和 y 都不是整數時， [x] + [y] 將介於 x + y – 2 和 x + y 之間。
回到原問題。
顯然，在第一個數列中，小於 n 的正整數有 [n / α] 個。顯然，在第二個數列中，小於 n 的正整數有 [n / β] 個。
因此，在這兩個數列中，小於 n 的正整數共有 [n / α] + [n / β] 個。
由於 α 和 β 都是無理數，因此 n / α 和 n / β 不可能為整數，由剛才的結論， [n / α] + [n / β] 一定介於 n / α + n / β – 2 和 n / α + n / β 之間，即 n – 2 和 n 之間。
但是， [n / α] + [n / β] 是個整數，因而它精確地等於 n – 1 。
這說明，前 n – 1 個正整數在兩個數列中一共出現了 n – 1 次，這對於所有 n 都成立。
於是，正整數 1 必須且只能出現在其中一個數列中，正整數 2 必須且只能出現在其中一個數列中，以此類推，每一個新的正整數都必須且只能出現在其中一個數列中。
這種取整函數的處理技巧也可以用到上一個問題裡：對上一個問題裡的數頭尾配對，你會發現每一對數之和都是 b – 1 。
12
問題：
把 10, 100, 1000, 10000, … 分別寫成二進制數和五進制數：
原數列：10, 100, 1000, 10000, 10000, …
二進制：1010, 1100100, 1111101000, 10011100010000, …
五進制：20, 400, 13000, 310000, 11200000, …
你會發現，對於任意正整數 n > 1 ，後兩個數列裡恰好有一個數是 n 位數。這是為什麼？
答案：
這是 Beatty-Rayleigh 定理的一個非常漂亮的直接推論。
10k 的二進制表達恰好有 [log210k] + 1 位，即 [k · log210] + 1 位。
10k 的五進製表達恰好有 [log510k] + 1 位，即 [k · log510] + 1 位。
我們只需要證明，數列 [1 · log210], [2 · log210], [3 · log210], … 和 [1 · log510], [2 · log510], [3 · log510], … 既無重複又無遺漏地包含了所有正整數。
注意到 log210 和 log510 是兩個倒數和為 1 的無理數，用一下 Beatty-Rayleigh 定理就出來了。
“超級數學建模”（微信號supermodeling），每天學一點小知識，輕鬆瞭解各種思維，做個好玩的理性派。60萬數學精英都在關注！
閱讀更多 超級數學建模 的文章
