3

Solve the diophantine equation 71x +29y = 101

1.Euclidean algorithm

71 = 29*2 + 13

29 = 29*2 + 3

13 = 3*4 + 1

3 = 3*1 + 0

GCD(71,29) = 1

2. Write as linear equation (Euclidean algorithm backwards)

1 = 13 - 4*3

3 = 29 - 2*13

13 = 71 - 2*29

1 = 13 - 4*3 =

= 13 -4*(29 - 2*13)

= 9*13 -4*29

= 9*(71-2*29)-4*29

= 9*71 - 22*29

1 = 9*71 - 22*29 -> (write in the form 71x +29y = 101)

71(9) + 29(-22) = 1

71(909) + 29(-2222) = 101

71*909 + 29*(-2222) + 29*71n - 71*29n = 101

71(909-29n) + 29(-2222 + 71n) = 101

x = 909 - 29n

y = -2222 + 71n

Now that's my solution. But the correct solution should be:

x = -29n - 19

y = 71n + 50

Daniel Andersson
  • 375
  • 2
  • 9
  • 1
    The $y$ solutions are the same since $-2222\equiv 50\pmod{71}$, but the $x$ solution is a bit off (I haven't scanned through your work yet, probably an arithmetic mistake). – Dave Apr 21 '19 at 19:27
  • I think you meant $x=-29n-19$ because then both solutions are equivalently correct. – Peter Foreman Apr 21 '19 at 19:28
  • Yes i meant - 19, but why are they equivalently correct? – Daniel Andersson Apr 21 '19 at 19:29
  • If the solution for $x$ has $-19$ instead of $-9$, then these are the same since $909\equiv -19\pmod{29}$. – Dave Apr 21 '19 at 19:30

1 Answers1

2

Both solutions are correct. They are just different parametrizations of the same set of $(x,y)$. You have got $$x=909-29n,y=-2222+71n$$ for any integer $n$. You can plug any integer for $n$ and still got valid solution. Especially we can replace $n$ with $n+c$ for some constant $c$, shifting the parameter and still get valid solutions. Doing this we would get $$x=909-29c-29n,y=-2222+71c+71n.$$ Now you can see that choosing $c=32$ gives $$x=-19-29n, y=50+71n,$$ the expected solution. You might think of this as just inserting as many multiples of $29$ or $71$ as needed to make the parametrization simpler, but keep in mind that the parameter $n$ is same in both equations for $x$ and $y$, so you need to change both accordingly. Perhaps sometimes it might be also useful to view the solution in vector form instead:

$$(x,y)=(909,-2222)+n\cdot(-29,71).$$

Sil
  • 16,612
  • How do we know that using c = -32 and c = 32 for both cases gives us the "best answer" – Daniel Andersson Apr 22 '19 at 16:11
  • There is no "best answer", it just explains how to get answer that your book/teacher got to. But still you could aim to get for example as small numbers as possible, which looks a bit better than large numbers, in that sense you would try $c$'s that minimize $909-29c$ and $-2222+71c$ in absolute value (by the way $c=-32$ does not give you anything "nice") – Sil Apr 22 '19 at 16:16
  • Ok, if a find a small number that looks good for y when c is something, must I then use the same c for x? (When using A mod B = (A + K*B) mod B for any integer K) – Daniel Andersson Apr 22 '19 at 16:34
  • Yes, it is the same $c$ as $n$ is the same $n$ in both equations. We have just substituted something into $n$, and you cannot substitute two different things for same $n$. – Sil Apr 22 '19 at 16:53