# Diophantine Equations Question

The question that I am working is:

Given the following diophantine equation: $53x + 12y = 2$ determine the integer solutions (if any).

The problem that I am facing is that I tried to find two solutions but keep getting an incorrect $x_{0}$ and $y_{0}$ values.

Here is my work: Claim - "Yes, integer solutions do exists."

Using Euclid's Algorithm:

$53 = 12(4) + 5$
$12 = 5(2) + 2$
$5 = 2(2) + 1$
$1 = 1(1) + 0$

Hence, $\text{gcd}(53,12) = 1$

System of equations:

$1 = 2 - 1(1)$
$1 = 5 - 2(2)$
$2 = 12 - 5(2)$
$5 = 53 - 12(4)$

## 2 Answers

If you just want to use basic algebra and common sense, take a look at the equation. Clearly $12y$ and $2$ are even so we have to have $53x$ even, so $x$ is even. A quick look and $x = -2$ will give $y = 9$, and $x = 10$ will give $y = -44$, now if you get the hang of it, keep on adding or subtracting $12$ to/from $x$ and other solutions will follow. Of course lab bhattacharjee's solution is more complete and rigorous, but this is one way such things can be dealt with intuitively.

Solution of Linear Congruence says solution always exists as $2$ is divisible by $(12,53)=1$

$$53x+12y=2=12\cdot9-2\cdot53$$

$$\iff53(x+2)=12(9-y)\iff\dfrac{53(x+2)}{12}=9-y$$ which is an integer

$\implies12|53(x+2)\iff12|(x+2)$ as $(12,53)=1$

$\implies x=12m-2$ where $m$ is any integer

Put this in $53x+12y=2$

• I do not know what linear congruence is. In lecture we have not learnt it so I can't use the method presented above.I need to solve the linear equations and that is what I am having trouble with.. – Arjun Dhiman Aug 16 '15 at 4:05
• @Zero, The solution does not need "linear congruence theorem"(linked). It has used basic concept of algebra if you ignore the first line, right? – lab bhattacharjee Aug 16 '15 at 4:08
• Yes, Im just using basic algebra nothing else. – Arjun Dhiman Aug 16 '15 at 4:08