Three strategies for integer problems: factorization, modular arithmetic, and bounds

What you will learn

Three useful starting points for integer problems, when to use each one, and how to write complete solutions.

How do you start an integer problem?

Integer problems can seem to depend on a flash of inspiration. I struggled with them as a high-school student too. A more practical starting point is to ask which of the following approaches the conditions suggest:

1. Factorization: turn an equation into a product and use its divisors.
2. Modular arithmetic: compare the possible remainders of both sides.
3. Bounds: reduce infinitely many candidates to a finite list.

These are useful strategies rather than an exhaustive classification of number theory. A single problem may require more than one.

Factorization: exploit divisors

Factorization is especially promising when primes, prime powers, or coprime integers appear. A prime $p$ has only the positive divisors $1$ and $p$. If a product equals a power of a prime, each positive factor must itself be a power of that prime.

For example, an equation of the form $(x-a)(y-b)=N$ reduces to checking factor pairs of $N$. Remember to include negative factors when the original variables are allowed to be negative.

Modular arithmetic: exploit remainders

When factorization does not help, look for a modulus that restricts one side strongly. An integer square is congruent to either $0$ or $1$ modulo $4$, and to either $0$ or $1$ modulo $3$. These small observations are often enough to rule out whole families of candidates.

The symbol $a\equiv b\pmod m$ means that $a-b$ is divisible by $m$.

Bounds: make the search finite

An inequality or the condition that a variable must be real can impose an upper bound on an integer. Once only finitely many possibilities remain, check them carefully.

For a symmetric expression, it is often useful to order the variables first. Then ask: which variable cannot be too large? If the smallest variable is already large, all the others are at least as large, which may contradict the required inequality.

Example 1: similar equations, different starting points

Find all pairs of positive integers $(k,n)$ satisfying each equation:

1. $3^n=k^3+1$.
2. $3^n=k^2-40$.

The first equation has a sum of cubes on the right, suggesting factorization. The second involves a square; working modulo $4$ will make factorization possible later.

Solution to part 1

Factorizing gives

$$3^n=(k+1)(k^2-k+1).$$

Since $k+1\ge2$ is a positive divisor of $3^n$, write

$$k+1=3^l,\qquad 1\le l\le n.$$

Substitute $k=3^l-1$ into the second factor:

$$k^2-k+1=3^{2l}-3^{l+1}+3=3(3^{2l-1}-3^l+1).$$

The integer in parentheses is congruent to $1$ modulo $3$, so this factor is divisible by $3$ exactly once. Comparing powers of $3$ in the product gives $n=l+1$. Consequently,

$$3^{2l-1}-3^l+1=1,$$

so $3^l(3^{l-1}-1)=0$. Hence $l=1$, $k=2$, and $n=2$.

Conversely, $3^2=2^3+1$. Therefore the only solution is

$$\boxed{(k,n)=(2,2).}$$

Solution to part 2

Work modulo $4$. If $k$ were even, $k^2-40\equiv0$, whereas $3^n\equiv1$ or $3$. Thus $k$ is odd. Then $k^2-40\equiv1$, so $n$ must be even.

Write $n=2m$, where $m$ is a positive integer. Now the equation factorizes:

$$(k-3^m)(k+3^m)=40.$$

Since $k^2=3^{2m}+40$, we have $k>3^m$. Both factors are therefore positive and even, with the second larger than the first. The only possibilities are

$$(k-3^m,k+3^m)=(2,20)\quad\text{or}\quad(4,10).$$

The first gives $k=11$ and $3^m=9$, hence $m=2$. The second gives $k=7$ and $3^m=3$, hence $m=1$. Both satisfy the original equation. Thus

$$\boxed{(k,n)=(11,4),\ (7,2).}$$

The key lesson is that modular arithmetic and factorization can work together: the remainder calculation exposes a difference of squares.

Example 2: a parity proof using squares modulo 4

Problem. Let $x,y,z,w$ be positive integers with

$$x^2+y^2+z^2=w^2.$$

Prove that at least two of $x,y,z$ are even.

Choosing a method

The conclusion concerns parity, while the equation contains squares. Modulo $4$ is more informative than modulo $2$: every even square has remainder $0$, and every odd square has remainder $1$.

Complete solution

Modulo $4$, each term among $x^2,y^2,z^2$ is $0$ or $1$, and $w^2$ is also $0$ or $1$.

If exactly two of $x,y,z$ were odd, the left side would have remainder $2$. If all three were odd, it would have remainder $3$. Both are impossible.

Therefore at most one of $x,y,z$ is odd. Equivalently, at least two are even.

Example 3: count integer triples by bounding the smallest variable

Problem. How many ordered triples of distinct positive integers $(l,m,n)$ satisfy

$$\frac1l+\frac1m+\frac1n>\frac85?$$

Choosing a method

The inequality is symmetric. First assume $l<m<n$, count the increasing triples, and then account for their permutations. If $l$ were too large, every reciprocal would be small, so bound $l$ first.

Complete solution

For $l<m<n$,

$$\frac85<\frac1l+\frac1m+\frac1n<\frac3l,$$

which gives $l<15/8$. Since $l$ is a positive integer, $l=1$. Hence

$$\frac1m+\frac1n>\frac35.$$

Since $1<m<n$, the left side is less than $2/m$, so $m<10/3$. Therefore $m=2$ or $m=3$.

• If $m=2$, then $1/n>1/10$, so $2<n<10$. There are seven possibilities: $n=3,4,5,6,7,8,9$.
• If $m=3$, then $1/n>4/15$, so $3<n<15/4$. There is no integer in that interval.

There are seven increasing triples. Each has three distinct entries and therefore $3!=6$ different permutations. The required number of ordered triples is

$$\boxed{7\times6=42.}$$

The word ordered matters: if permutations were considered the same, the answer would be seven.

A checklist for your next problem

Look for a product when primes or divisibility appear. Try a small modulus when powers or parity appear. If neither immediately resolves the problem, look for inequalities that force a finite search. Always substitute the surviving candidates into the original conditions to establish that they really are solutions.

For a different kind of method selection, see how symmetry simplifies probability recurrences.