求能被 15 整除的最大六位迴文數。

Step-by-step solution

1. 1

   先寫出六位迴文數的長相。 任何這樣的數都長成

   $\overline{abccba}$

   其中 $a,b,c$ 為數字且 $a\neq 0$。只有三個自由的數字而不是六個——光這一點就把搜尋範圍從 $900{,}000$ 個數縮小到 $900$ 個。

2. 2

   把整除條件拆開。 因為 $15=3\times 5$ 且 $\gcd(3,5)=1$，一個數能被 $15$ 整除，充要條件是同時能被 $3$ 與 $5$ 整除。把兩個質因數分開處理，這題才可能用手算完成。

3. 3

   用被 5 整除的規則定出首位。 被 $5$ 整除要求末位是 $0$ 或 $5$。而在迴文數裡末位等於首位，六位數的首位又不能是 $0$，所以

   $a=5$

   這個數的形狀是 $\overline{5bccb5}$。因此所有候選都落在五十幾萬的範圍——不可能有以 $6$ 或更大開頭的 $15$ 的倍數迴文數。

4. 4

   把被 3 整除的規則用在數字和上。 各位數字之和為

   $5+b+c+c+b+5=10+2b+2c$

   它必須是 $3$ 的倍數。對 $3$ 取模，$10+2b+2c\equiv 1+2(b+c)\equiv 0$，於是逼出

   $b+c\equiv 1 \pmod 3$

5. 5

   從左邊開始把數字取到最大。 越前面的位權越大，所以先試 $b=9$。此時 $c$ 必須滿足 $9+c\equiv 1\pmod 3$，即 $c\equiv 1\pmod 3$，所以 $c\in\{1,4,7\}$，最大取 $c=7$。這也說明了為什麼看起來很誘人的 $599995$ 不行：它的數字和是 $46$，不是 $3$ 的倍數。

6. 6

   組合起來並驗算。 取 $a=5$、$b=9$、$c=7$，得到

   $597795$

   驗算：末位是 $5$，能被 $5$ 整除；數字和為 $5+9+7+7+9+5=42$，能被 $3$ 整除；而且確實有

   $597795=15\times 39853$

   由於 $b=9$ 已是第二位能取的最大值、$c=7$ 是第三位可行的最大值，所以不存在更大的六位迴文數符合條件。