Find the largest six-digit palindrome that is divisible by 15.

Step-by-step solution

1. 1

   Write down the shape of a six-digit palindrome. Any such number looks like

   $\overline{abccba}$

   with digits $a,b,c$ and $a\neq 0$. Three free digits instead of six — that alone cuts the search from $900{,}000$ numbers to $900$.

2. 2

   Split the divisibility condition. Since $15=3\times 5$ and $\gcd(3,5)=1$, a number is divisible by $15$ exactly when it is divisible by both $3$ and $5$. Handling the two prime factors separately is what makes the problem doable by hand.

3. 3

   Use the rule for 5 to pin down the first digit. Divisibility by $5$ requires the last digit to be $0$ or $5$. In a palindrome the last digit equals the first, and a six-digit number cannot start with $0$, so

   $a=5$

   and the number has the form $\overline{5bccb5}$. Every candidate therefore starts in the $5$-hundred-thousands — no palindrome multiple of $15$ can begin with $6$ or higher.

4. 4

   Apply the rule for 3 to the digit sum. The digits sum to

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

   This must be divisible by $3$. Working modulo $3$, $10+2b+2c\equiv 1+2(b+c)\equiv 0$, which forces

   $b+c\equiv 1 \pmod 3$

5. 5

   Maximise the digits from the left. The leading digits weigh most, so try $b=9$ first. Then $c$ must satisfy $9+c\equiv 1\pmod 3$, i.e. $c\equiv 1\pmod 3$, so $c\in\{1,4,7\}$ and the largest is $c=7$. This is also why the tempting $599995$ fails: its digit sum is $46$, not a multiple of $3$.

6. 6

   Assemble and verify. With $a=5$, $b=9$, $c=7$ the number is

   $597795$

   Check: it ends in $5$, so it is divisible by $5$; its digits sum to $5+9+7+7+9+5=42$, divisible by $3$; and indeed

   $597795=15\times 39853$

   Since $b=9$ is the largest possible second digit and $c=7$ the largest admissible third digit, no larger six-digit palindrome works.