[Competitive Programming] Number Theory

A running collection of number theory facts that turn a search problem into a one-liner — one section per trick, added to over time.

Contents

1. Even-length palindromes are divisible by 11 — so 11 is the only palindromic prime with an even number of digits. (CodeChef MD_RIEV)
2. Every divisibility rule is one congruence — find what \(10^k\) is congruent to mod your target and the rule falls out.

Even-length palindromes are divisible by 11

Take any palindrome with an even number of digits:

Every single one is a multiple of 11:

This is not a coincidence, and the proof is three lines.

The divisibility rule for 11

Everything follows from one congruence:

Write a number by its digits, indexing from the least significant digit:

Reducing mod 11 and using \(10^i \equiv (-1)^i\):

So \(11 \mid n\) exactly when the alternating sum of the digits is zero mod 11. That’s the familiar rule: add the digits in even positions, subtract the digits in odd positions, check if the result is a multiple of 11.

The palindrome argument

Let \(n\) be a palindrome with \(2m\) digits. Palindromicity says

Now look at the two indices in each pair. They sum to

which is odd. Two integers summing to an odd number must have opposite parity. So each pair consists of one even index and one odd index — carrying the same digit.

The map \(i \mapsto 2m-1-i\) has no fixed point (a fixed point would need \(2i = 2m-1\), impossible for an integer), so it partitions all \(2m\) positions into exactly \(m\) disjoint pairs. Each pair contributes \(+d_i - d_i = 0\) to the alternating sum. Therefore

Concretely, for \(4554\):

The palindrome hands you the cancellation for free.

Why odd length is different

For odd length the same pairing leaves one digit stranded in the middle, and it pairs \(i\) with \(2m-i\) — indices of the same parity, so they add instead of cancelling. Nothing collapses:

• \(121 = 11^2\) — divisible by 11, but by accident
• \(131\) — prime
• \(151\) — prime
• \(313\) — prime

Odd-length palindromes are unconstrained, which is exactly why all the interesting palindromic primes live there.

The corollary that matters

An even-length palindrome \(n\) satisfies \(11 \mid n\) and \(n \ge 11\). If \(n\) is also prime, its only divisors are 1 and itself, so \(n = 11\).

11 is the only palindromic prime with an even number of digits.

The full list of palindromic primes starts:

One even-length entry, then never again — no matter how far you go.

Application — CodeChef MD_RIEV

Palindromic Prime Numbers (CodeChef Starters 108) asks:

Consider the first \(N\) palindromic prime numbers. How many of them have an even number of digits, and how many have an odd number of digits?

Without the fact above this looks like it needs a sieve, a palindrome check, and some bound on how far you have to search to collect \(N\) of them — and \(N\) can be large enough that you can’t actually generate them.

With the fact, the answer is a case split on where 11 sits in the ordering. The palindromic primes in order are \(2, 3, 5, 7, 11, 101, \dots\) — so 11 is the 5th one, and it is the only even-length one that will ever appear.

• \(N \le 4\): you haven’t reached 11 yet → 0 even, N odd
• \(N \ge 5\): you have exactly one even-length one → 1 even, N - 1 odd

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        if (n <= 4) cout << 0 << " " << n << "\n";
        else        cout << 1 << " " << n - 1 << "\n";
    }
    return 0;
}

\(O(1)\) per test case. No sieve, no palindrome check, no precomputation.

The lesson generalises past this problem: when a counting problem is about primes and some digit structure, check whether the digit structure forces a divisor. If it does, the “primes” half of the problem usually collapses to a handful of small cases.

In other bases

Nothing about the argument was specific to base 10. In base \(b\):

so the identical alternating-sum argument gives:

In base \(b\), every even-length palindrome is divisible by \(b + 1\).

Which means in base \(b\), the only even-length palindromic prime is \(b + 1\) itself — and only when \(b+1\) is prime.

Binary is a nice sanity check: \(11_2 = 3\), \(1001_2 = 9\), \(1111_2 = 15\), \(100001_2 = 33\) — all multiples of 3.

Quick reference

Every divisibility rule is one congruence

Every schoolbook divisibility rule is the same move: find what \(10\) (or a power of it) is congruent to, mod your target.

The \(1001 = 7 \cdot 11 \cdot 13\) row is the underused one. Since \(10^3 \equiv -1 \pmod{1001}\), group the digits in threes from the right and alternate:

and \(334\) is not divisible by 7, 11, or 13 — so neither is \(1234567\). One computation resolves three moduli at once.