| taking modulo. enumerating solutions |
| |
\item factoring (SFFT) |
| |
\item infinite descent |
| |
\item Iurie's ``parameterization" trick. (IMO ??/6: Let $a>b>c>d$ be positive integers and suppose |
| |
\[ |
| |
ac+bd=(b+d+a-c)(b+d-a+c). |
| |
\] |
| |
Prove that $ab+cd$ is not prime. |
| |
\item Constructing solutions |
| |
\item |
| |
geometric methods (Minkowski) |
| |
\end{enumerate} |
| |
\end{enumerate} |
| |
|
| |
\section{Linear Diophantine Equations} |
| |
An equation of the form |
| |
\begin{equation} |
| |
a_1 x_1+ \dots + a_n x_n =b, \label{eq1} |
| |
\end{equation} |
| |
where $a_1,\dots,a_n,b \in \mathbb{Z}$ is called linear diophantine |
| |
equation. |
| |
|
| |
\begin{thm} |
| |
The equation (\ref{eq1}) is solvable if and only if |
| |
$\gcd(a_1,\dots,a_n)\mid b$. |
| |
\end{thm} |
| |
|
| |
\begin{proof} |
| |
Let $d=\gcd(a_1,\dots,a_n)$. If $d\nmid b$ the equation is not |
| |
solvable. If $d\mid b$ we denote $a_i'=\cfrac{a_i}{d}, \ |
| |
b'=\cfrac{b}{d}$. Then $\gcd(a_1',\dots,a_n')=1$ and the generalized |
| |
B\'{e}zout Lemma says that there exist $x_i'$ such that |
| |
$a_1'x_1'+\dots +a_n' x_n'=1$, which implies $a_1x_1'+\dots |
| |
+a_nx_n'=d$. We obtain $a_1(b'x_1')+\dots +a_n(b'x_n')=b'd=b.$ |
| |
\end{proof} |
| |
|
| |
\begin{cor} |
| |
Let $a_1,a_2$ be relatively prime integers. If $(x_1^0,x_2^0)$ is a |
| |
solution to the equation |
| |
$$a_1x_1+a_2x_2=b, $$ |
| |
then all its solutions are given by |
| |
\begin{equation*} |
| |
\begin{cases} |
| |
x_1=x_1^0+a_2 t \\ |
| |
x_2=x_2^0-a_1 t |
| |
\end{cases} |
| |
,t\in \mathbb{Z}. |
| |
\end{equation*} |
| |
\end{cor} |
| |
|
| |
\begin{prb} |
| |
Solve the equation |
| |
$$15x+84y=39. $$ |
| |
\end{prb} |
| |
|
| |
\begin{proof} |
| |
The equation is equivalent to $5x+28y=13$. A solution is $y=1, \ |
| |
x=-3$. All solutions are of the form $x=-3+28 |
