Linear Diophantine equations

In how many different ways can you change one dollar? That is, in how many different ways can you pay 100 cents using five different kinds of coins, cents, nickels, dimes, quarters and half-dollars (worth 1, 5, 10, 25, and 50 cents, respectively)?

Let $n$ stand for a non-negative integer and let $A_n$ denote the number of solutions of the Diophantine equation

in non-negative integers. Then the series

represents a rational function of $\zeta$. Find it.

Generalize the preceding examples by replacing the particular values of the coins, stamps and weights by $a_1, a_2, \ldots , a_l$.

The total number of non-negative integral solutions of the following Diophantine equations is $n+1$:

The total number $N$ of non-negative integral solutions of the following Diophantine equations

is smaller than $n+2$; moreover the difference $n+2-N$ is equal to the number of divisors of $n+2$ (cf. Part VIII, Chapter 1, §5).

Prove that the total number of non-negative integral solutions of the following Diophantine equations is $n$:

The number of non-negative solutions of the Diophantine equation

is equal to the integer closest to $\frac{(n+3)^2}{12}$.

Let $a$, $b$ and $n$ be positive integers, $a$ and $b$ relatively prime to each other. The number of non-negative integral solutions of the equation

is equal to $\left[\frac{n}{ab}\right]$ or $\left[\frac{n}{ab}\right]+1$.

Let $n \geq 3$. The number of positive integral solutions of

that satisfy the additional conditions

is given by

Prove that if a square integer system of linear equations has a unique solution modulo every prime number $p$, then it also has a unique solution over the ring of integers.

Determine whether a square integer system of linear equations that is consistent modulo every prime number $p$ is necessarily consistent over the ring of integers.

Two sets of unknowns are called integrally equivalent if they are related by

where $U$ is an integer matrix whose determinant is equal, in absolute value, to 1. Prove that the system of equations

where $a_{i j}, b_{i}$ are integers, is equivalent, over the ring of integers, to a system of equations of the form

where the set of unknowns $\left(y_{1}, \ldots , y_{n}\right)$ is integrally equivalent to the set $\left(x_{1}, \ldots , x_{n}\right)$.

Prove that an integer system of equations has an integer solution if and only if, for every natural number $k$, the greatest common divisors of all minors of order $k$ in the matrix of the system and in its augmented matrix coincide.

Prove that an integer system of equations has an integer solution if and only if it has a solution modulo every prime $p$.

Justify the following practical method for finding all integer solutions of a system of equations

with integer coefficients. Construct the matrix $\left(\begin{array}{cc}A & b \\ E_{n} & 0\end{array}\right)$ of size $(n+m) \times (n+1)$. Then, using only integer elementary transformations of the first $m$ rows and $n$ columns, reduce this matrix to the form $\left(\begin{array}{cc}D & C \\ U & 0\end{array}\right)$, where $C=\left(\begin{array}{c}c_{1} \\ \vdots \\ c_{m}\end{array}\right), \quad \left|\operatorname {det} U\right|=1, \quad D=\left(\begin{array}{ccccccc}d_{1} & 0 & \ldots & 0 & 0 & \ldots & 0 \\ 0 & d_{2} & \ldots & 0 & 0 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & \ldots & d_{r} & 0 & \ldots & 0 \\ 0 & 0 & \ldots & 0 & 0 & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & \ldots & 0 & 0 & \ldots & 0\end{array}\right)$, $d_{i} \mid d_{i+1}, \quad d_{1} \neq 0, \ldots , d_{r} \neq 0$. Then the system is consistent if

and the general solution is given by the formula

where $y_{r+1}, y_{r+2}, \ldots , y_{n}$ are arbitrary integers.

Find all integer solutions of the following systems of equations: