1
$\begingroup$

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)$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – Arjun Dhiman Aug 16 '15 at 4:05
  • $\begingroup$ @Zero, The solution does not need "linear congruence theorem"(linked). It has used basic concept of algebra if you ignore the first line, right? $\endgroup$ – lab bhattacharjee Aug 16 '15 at 4:08
  • $\begingroup$ Yes, Im just using basic algebra nothing else. $\endgroup$ – Arjun Dhiman Aug 16 '15 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.