Integral Solutions

At a glance 11 formulas

1. 1When solutions exist$ax + by = c$ has integer solutions only when $\gcd(a, b)$ divides $c$: $6x + 9y = 20$ has none, since 3 does not divide 20.
2. 2Find one, then step$x = x_0 + bt,\quad y = y_0 - at$$\text{for } ax + by = c,\ \gcd(a, b) = 1$
3. 3Use a remainderWork modulo one coefficient: in $7x + 5y = 100$ every other term is a multiple of 5, so $7x$ is too, and $x$ is a multiple of 5.
4. 4Count within limitsWrite $x$ and $y$ in terms of $t$, turn each limit into a range of $t$, and count the values of $t$ that meet every limit at once.
5. 5Positive parts$x_1 + x_2 + \cdots + x_k = n:\ \dbinom{n-1}{k-1}$
6. 6Non-negative parts$x_i \ge 0:\ \dbinom{n+k-1}{k-1}$
7. 7Lower limits firstFor $x \ge 3$, hand out the 3 first: put $x = x' + 3$, take 3 off the total, then count with $x' \ge 0$.
8. 8Less than or equalTurn $x + y + z \le n$ into an equation with a slack $s = n - (x + y + z) \ge 0$, then count $x + y + z + s = n$.
9. 9Product equationsRewrite $xy + ax + by = c$ as $(x + b)(y + a) = c + ab$, then count factor pairs, including negative ones that keep $x$ and $y$ in range.
10. 10Reciprocal sums$\tfrac{1}{x} + \tfrac{1}{y} = \tfrac{1}{n} \iff (x-n)(y-n) = n^{2}$$\text{positive ordered pairs} = \text{divisors of } n^{2}$
11. 11Difference of squares$x^{2} - y^{2} = N$ means $(x - y)(x + y) = N$: each factor pair $d < \tfrac{N}{d}$ with both odd or both even gives one positive pair.