-1
$\begingroup$

How do you use the Euclidean Algorithm to solve the following: Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$

$\endgroup$

closed as off-topic by T. Bongers, John Omielan, mrtaurho, GNUSupporter 8964民主女神 地下教會, Delta-u Feb 28 at 9:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – T. Bongers, John Omielan, mrtaurho, GNUSupporter 8964民主女神 地下教會, Delta-u
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Look online for linear diophantine equations of degree 1... $\endgroup$ – Bruno Reis Feb 28 at 4:07
  • $\begingroup$ $261x+48y=7881$ iff $87x+16y=2627$ $\endgroup$ – J. W. Tanner Feb 28 at 4:21
  • $\begingroup$ solutions are (5,137) and (21,50) $\endgroup$ – J. W. Tanner Feb 28 at 4:33
2
$\begingroup$

Euclidean algorithm:

$261=5\times48+21$

$48=2\times21+6$

$\color{blue}{21}=3\times6+3$

so $\color{blue}{(261-5\times48)}=3\times(48 - 2\color{blue}{(261-5\times48)})+3;$

i.e., $7\times261-38\times48=3.$

Therefore, $2627\times7\times261-2627\times38\times48=3\times2627=7881;$

i.e., $18389\times261-99826\times48=7881.$

More generally $(18389-16k)\times261+(87k-99826)\times48=7881.$

$18389-16k>0$ and $87k-99826 > 0$ were requested.

Thus $k < 1149.3125$ and $k > 1147.4...$; i.e., $k = 1148$ or $1149.$

Solutions are therefore $21\times261+50\times48=7881$ and $5\times261+137\times48=7881.$

$\endgroup$
  • $\begingroup$ You missed positive $\endgroup$ – Bill Dubuque Feb 28 at 4:17
  • $\begingroup$ Oops.................... $\endgroup$ – J. W. Tanner Feb 28 at 4:18
  • $\begingroup$ Corrected...... $\endgroup$ – J. W. Tanner Feb 28 at 4:46

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