For all positive integers n, the function rev(n) reverses the digits of n. For example, rev(205) = 502 and rev(12340) = 04321 = 4321. Compute the least positive integer m such that gcd(m, rev(m)) = 13.
Two digit N are easy enough to list: 13, 26, 39, 52, 65, 78, 91 are the two digit multiples of 13 but none of them remain multiples of 13 when the digits are reversed.
For N and rev(N) to have a GCD of 13 then they must both necessarily be multiples of 13. Furthermore their sum and difference must also be multiples of 13.
For three digit N, let N=ABC and then rev(N)=CBA. Then N-rev(N) = (A-C)*99. This needs to be a multiple of 13, but that can happen when A=C.
But then N=rev(N) and their GCD will be ABA, not just 13. So no three digit solutions either.
Onto four digit N. Then rev(N)=DCBA.
Now N+rev(N) = 1001*(A+D) + 11*(B+C). 1001 is a multiple of 13 so for the whole sum to be a multiple of 13 we need to have B+C=13.
Only six cases to consider: (B,C) = (4,9), (5,8), (6,7), (7,6), (8,5), (9,4). Since we are seeking the smallest then (B,C) = (4,9) will be the first place to look
If N=A49D, then N-rev(N) = (A-D)*999-450 needs to be a multiple of 13. Then A-D=9 mod 13, or equivalently, D-A=4 mod 13. So (A,D) could be (1,5), (2,6), (3,7), (4,8), (5,9), or (9,0).
ABCD=1495, 2496, 3497, 4498, 5499, or 9490. Of these the ones with GCD(N,rev(N))=13 are 1495 and 3497.
1495 has the smallest possible A and B values so it is the least positive integer m such that gcd(m, rev(m)) = 13.
Analytic Solution
