Given such that Prove that

Question by Summer Clouds

13/10/2017 at 10:07

Ka Yoo Mi 15/10/2017 at 19:19

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