Math and Number Theory

Tactic

Math and number theory use arithmetic structure instead of search. Divisibility, remainders, digit behavior, and identities can replace loops over candidates.

The invariant is a numeric property that stays true across transformations. Examples include gcd preserving common divisors, modular equivalence preserving remainders, and exponentiation by squaring preserving the product represented by processed bits.

The first move is to rewrite the prompt as an equation or congruence. Once the equation is visible, the algorithm is often a short loop over digits, factors, bits, or remainders.

Value

The value is eliminating unnecessary enumeration. A formula, gcd, modulo class, or logarithmic exponentiation can reduce work by orders of magnitude.

Direct complexity example

Brute force: Try every divisor, repeated multiplication, or every numeric candidate: $O(n)$ or worse depending on the value range.
With this tactic: Use gcd, modulo arithmetic, digit loops, or exponentiation by squaring: often $O(\log n)$ or $O(\sqrt n)$ time depending on the operation.
Space: Space is usually $O(1)$ , unless storing factors, primes, or large intermediate strings is required.

Challenges this solves

gcd of strings
power function
reverse integer
happy number
pairs divisible by k
manual arithmetic on strings

When to use it

Use this tactic when these conditions are true:

the prompt mentions divisibility, remainder, digits, powers, gcd, or modulo
the input values are large but their arithmetic structure is small
checking all candidates is too slow
a known identity preserves the answer

When not to use it

Reach for a different tactic when these warning signs appear:

the problem is really about ordering or traversal
numeric overflow or precision changes the rules
a formula is guessed without proof
constraints are tiny and direct simulation is clearer

Terminology clues

These prompt words often point toward this concept:

divisible
modulo
remainder
gcd
prime
power
digits
integer