๐ Solvability of Linear Diophantine Equations
The equation $ax + by = c$ has integer solutions if and only if $\\gcd(a,b)$ divides $c$.
Proof: (โน) If $x, y$ are solutions, then $\\gcd(a,b)$ divides $ax + by = c$.
(โธ) Suppose $d = \\gcd(a,b)$ divides $c$. Write $c = dk$.
By the Linear Representation Theorem, $d = ax_0 + by_0$ for some integers.
Then $c = dk = a(kx_0) + b(ky_0)$.
So $x = kx_0$ and $y = ky_0$ is a solution.
From: numbers-geometry
Learn more:
Explore all courses: 

Magic Internet Math
Interactive courses covering the mathematics that powers modern technology, from foundational algebra to the cryptography securing the internet.

Magic Internet Math
Interactive courses covering the mathematics that powers modern technology, from foundational algebra to the cryptography securing the internet.