Linear diophantine equations

Diophantus, a Greek mathematician who lived during the 4th century A.D., was one of the first people who attempted to find integral or rational solutions to a given system of equations. Often the system involves more unknowns than equations. We will consider a linear equation, $ax+by=c$, with two unknowns $x,y$.

Theorem 1.2.17   The linear equation $ax+by=c$ has no solutions if $gcd(a,b)$ does not divide $c$. If $gcd(a,b)$ does divide $c$ then there are infinitely many solutions given by:

$$x=x_0+ \frac{b}{gcd(a,b)}\,t, \quad y=y_0-\frac{a}{gcd(a,b)}\,t ,$$

where $x=x_0$, $y=y_0$ is any solution and $t$ is any integer.

proof: The first part of the theorem follows from lemma 1.2.4. Let $x=x_0$, $y=y_0$ be any solution, and let $x=r,\,y=s$ be any other solution. We want to show that $r=x_0+\frac{b}{d}t$ and $s=y_0-\frac{a}{d}\,t$, where $d=gcd(a,b)$. Substitute into the equation: $ax+by=c$:

$$0=c-c=ar+bs-(ax_0+by_0)=a(r-x_0)+b(s-y_0).$$

Therefore, $a(r-x_0)=b(y_0-s)$. If $d > 1$ we can divide both sides of this equation by $d$:

$$\frac{a}{d}(r-x_0)=\frac{b}{d}(y_0-s).$$

Since $(\frac{a}{d},\frac{b}{d})=1$ (see the Exercise 1.2.24), it follows that $\frac{a}{d} \,\mid (y_0-s)$. Substituting $y_0-s=\frac{a}{d}\,t$ into the above equation gives:

$$r-x_0=\frac{d}{a}\,\frac{b}{d}\,(y_0-s) =\frac{b}{a}\,t\,\frac{a}{d}=\frac{b}{d} t ,$$

and our proof is complete. $\Box$

Corollary 1.2.18   If $a \,\mid \,bc$ then $a \,\mid \,(a,b)c$.

proof: Assume $a\,\mid bc$. Let $d=(a,b)$. By the above theorem, there exist integers $x$, $y$ such that $ax+by=d$ $, so acx+bcy=dc$. Since $a$ divides $acx$ and $a$ divides $bcy$, by the hypthothesis, it divides $acx+bcy$, by Lemma 1.2.4. Therefore $a \,\mid \,(a,b)c$. $\Box$

The following corollary is an immediadiate consequence of the previous one.

Corollary 1.2.19   If $a \,\mid \,bc$ and $(a,b)=1$ then $a\mid c$.

Exercise 1.2.20   Find all integers $d>0$ such that $12 \mid d$ and $d \mid 260$.

Exercise 1.2.21   Find $q$ and $r$ guaranteed by the division algorithm for $a=28$ and $b=160$.

Exercise 1.2.22   Prove the claim in the first proof of the division algorithm, theorem 1.2.7.

Exercise 1.2.23   For any integer $n$, prove that:

(a) $2$ divides $n(n+1)$,

(b) $3$ divides $n(n+1)(n+2)$.

Exercise 1.2.24   Prove that if $d=gcd(a,b)$ then $gcd(\frac{a}{d},\frac{b}{d})=1$. (In other words, $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime.)

Exercise 1.2.25  

Exercise 1.2.26   Prove that every square integer is of the form $4k$ or $4k+1$, where $k$ is an integer.

Exercise 1.2.27   Prove that $4$ does not divide $n^2+2$, for any integer $n$.

Exercise 1.2.28   Prove that if $3$ does not divide an odd integer $n$, then 24 divides $n^2-1$.

Exercise 1.2.29   Find

(a) $lcm(6,21)$,

(b) $lcm(10,15)$,

(c) $gcd(99,100)$.

(d) $gcd(24,78)$,

(e) $lcm(24,78)$.

Exercise 1.2.30   Suppose $a>1$ is an odd integer. Find a formula for $lmc(a,a+2)$.

Suppose $a>1$ is an even integer. Find a formula for $lmc(a,a+2)$.

Exercise 1.2.31   Verify that (6) in Proposition 1.2.16 is true.

Exercise 1.2.32   Verify that (8) in Proposition 1.2.16 is true.

Exercise 1.2.33   Verify that (9) in Proposition 1.2.16 is true.

Exercise 1.2.34   Suppose $a>1$ is an integer. Find $gcd(a,a+1)$.

Exercise 1.2.35   Suppose $a>1$ is an odd integer. Find $gcd(a,a+2)$.

Suppose $a>1$ is an even integer. Find $gcd(a,a+2)$.

Exercise 1.2.36 (a)   Find $gcd(51,15)$.

(b) Find $gcd(51,105)$.

(c) Find $gcd(501,105)$.

Exercise 1.2.37   Let $$\left( \begin{array}{c} n \\ k \end{array}\right)={n!\over k!(n-k)!}$$ denote the combinatorial symbol $n$ choose $k$ (also called a binomial coefficient), where $m!=1\cdot 2\cdot ... \cdot m$ is $m$ factorial. This is the coefficient of $x^ky^{n-k}$ in the binomial expansion of $(x+y)^n$,

$$(x+y)^n=x^n+\left( \begin{array}{c} n \\ 1 \end{array}\righ... ...ft( \begin{array}{c} n \\ n-1 \end{array}\right)x^{n-1}y+y^n.$$

These can be computed by hand using Pascal's triangle,

$$1$$

$$1 \ \ \ \ \ \ 1$$

$$1 \ \ \ \ \ \ 2 \ \ \ \ \ \ 1$$

$$1 \ \ \ \ \ \ 3 \ \ \ \ \ \ 3 \ \ \ \ \ \ 1$$

$$1 \ \ \ \ \ \ 4 \ \ \ \ \ \ 6 \ \ \ \ \ \ 6 \ \ \ \ \ \ 4 \ \ \ \ \ \ 1$$

$$1 \ \ \ \ \ \ 5 \ \ \ \ \ \ 10 \ \ \ \ \ \ 10 \ \ \ \ \ \ 5 \ \ \ \ \ \ 1$$

$$1 \ \ \ \ \ \ 6 \ \ \ \ \ \ 15 \ \ \ \ \ \ 20 \ \ \ \ \ \ 15 \ \ \ \ \ \ 6 \ \ \ \ \ \ 1$$

$$...$$

Check $$5\vert \left( \begin{array}{c} 5 \\ k \end{array}\right)$$, for $k=1,2,3,4$.

Exercise 1.2.38   Factor all the integers $100,101,102,103,104,105$.

Exercise 1.2.39   Show that $$7\vert \left( \begin{array}{c} 7 \\ k \end{array}\right)$$, for $k=1,2,3,4,5,6$. Show that $$11\vert \left( \begin{array}{c} 11 \\ k \end{array}\right)$$, for $k=1,2,...,10$. Is there some $k=1,2,...,8$ such that $$9\vert \left( \begin{array}{c} 9 \\ k \end{array}\right)$$?