Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

If $(a,b)\mid c$, $\exists t\in \mathbb{Z}$ such that $t(a,b)=c$. As we know that there exists $x,y \in \mathbb{Z}$ such that $ax+by=(a,b)$, then choose the integers $x_0=tx$ and $y_0=ty$.

To prove the converse, if $x_0$ and $y_0$ be integers, then $(a,b)\mid x_0a$ and $(a,b)\mid y_0y$ implies $(a,b)\mid (x_0a+y_0b)$.

Tags:

Discrete Mathematics

Diophantine Equations

Elementary Number Theory

Divisibility

Related

Interview puzzle with a deck of cards, some cards upside-down Why use Gauss Jordan Elimination instead of Gaussian Elimination, Differences Reverse Cauchy Schwarz for integrals Does de Rham theorem hold for manifolds with boundary? $f$ is twice differentiable, $f + 2 f^{'} + f^{''} \geq 0$ , prove the following How do you calculate this limit $\lim_{n\to\infty}\sum_{k=1}^{n} \frac{k}{n^2+k^2}$? If $\lambda$ is an eigenvalue of $A^2$, then either $\sqrt{\lambda}$ or $-\sqrt{\lambda}$ is an eigenvalue of $A$ Matrix exponential of a skew-symmetric matrix without series expansion $F/K$ algebraic and every nonconstant polynomial in $K[X]$ has a root in $F$ implies $F$ is algebraically closed. Prove $_2F_1\left(\frac13,\frac13;\frac56;-27\right)\stackrel{\color{#808080}?}=\frac47$ Why does this infinite series equal one? $\sum_{k=1}^\infty \binom{2k}{k} \frac{1}{4^k(k+1)}=1$ How to find an angle in range(0, 360) between 2 vectors?

Recent Posts