Answers ( 1 )

---

• See question detail

  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
• View more →

Questions ( 0 )

---

• View more →