Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone please tell me how to do this question? I have absolutely no idea how to go about solving this problem.

Find all the integer solutions of the equation: $$246x + 217y = 3$$

Thank you very much for all your help.

share|improve this question
4  
You can simplify the equation observing that all the coefficients are divisible by 3. Then apply the Euclidean algorithm en.wikipedia.org/wiki/Extended_Euclidean_algorithm to compute a solution, and finally use Bezout's identity en.wikipedia.org/wiki/Bézout's_identity to compute all of them. –  Giovanni De Gaetano Jul 1 '13 at 13:24
    
@GiovanniDeGaetano: $217\equiv 1\pmod{3}$ –  Tomas Jul 1 '13 at 13:43
    
Ooops, Clearly $7+1+2\neq 9$ then! I apologize for the mistake... ...in this case we simply observe that $3/3$ and $3/246$ implies that $3/y$ for any solution $y$. So all the solutions are of the form $(x_0,3y_0)$ where $(x_0,y_0)$ is a solution of $\frac{246}{3}x +217y =\frac{3}{3}$. The strategy of the comment above applies to this equation. PS @Tomas, thanks for pointing it out! –  Giovanni De Gaetano Jul 1 '13 at 14:43
add comment

3 Answers

Using the Euclid-Wallis Algorithm, we get $$ \begin{array}{r} &&1&7&2&14\\\hline 1&0&1&-7&15&-217\\ 0&1&-1&8&-17&246\\ 246&217&29&14&1&0 \end{array} $$ That is $15\cdot246-17\cdot217=1$ is a particular solution. Multiplying by $3$ and applying the homogenous solution gives the general solution: $$ (45-217k)246+(-51+246k)217=3 $$

share|improve this answer
add comment

We can see that x and y cannot consecutively positive or negative. So x and y should have alternate signs else it would not be an integer. Also, the slope of line is negative, that means that the line must have touched the 2nd and 4th quadrant, so your answers also must lie there. And if you plot the graph(just for verification), you can verify the above. So all your answers lie in the 2nd and 4th quadrant.

Now according to me there are very less solutions for the above, so you may do the above using a graphical calculator, or may think that for what x, $\frac{3-246x}{217}$ is an integer or for what x, $3-246x$ is divisible by 217.

share|improve this answer
add comment

Expressing as continued fraction, $$\frac{246}{217}=1+\frac{29}{217}=1+\frac1{\frac{217}{29}}=1+\frac1{7+\frac{14}{29}}=1+\frac1{7+\frac1{\frac{29}{14}}}=1+\frac1{7+\frac1{2+\frac1{14}}}$$

So, the previous convergent of $\frac{246}{217}$ is $1+\frac1{7+\frac1{2}}=\frac{17}{15}$

Using Theorem $3$ (here) of continued Fraction, $246\cdot15-17\cdot217=1$

So, $246x+217y=3=3(246\cdot15-17\cdot217)$

$\implies \frac{246(x-3\cdot15)}{217}=-(17\cdot3+y)$ which is an integer

$\implies 217$ divides $246(x-3\cdot5)$

$\implies 217$ divides $(x-45)$ as $(217,246)=1$

$\implies x=45+217c$ where $c$ is any integer

Similarly, $y=-246c-51$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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