A friend and I are in an intro to number theory class at UK and were struggling to prove the theorem that states that for two relatively prime integers $a$ and $b$ there exist integers x and y which satisfy the equation $ax+by=1$. We have now proven the theorem but while attempting to prove it began generating lists of relatively prime pairs with the same difference i.e. $(2,7)$, $(3,8)$, $(4,9)$..., and noticed patterns emerging in the solutions such as for differences of $5$:

(a,b)  (x,y)
(2,7)  (-3,1)
(3,8)  (3,-1)
(4,9)  (-2,1)
(6,10) (2,-1)

We are attempting to find a rule which will quickly generate a solution for any given pair, even of large numbers, not only for the differences of $5$ but for every given difference n. Any suggestions? Have you heard of this before?

  • $\begingroup$ sorry the part in the middle looks a little confusing let me clarify it should read as for (2,7), (x,y)=(-3,1), for (3,8), (x,y)=(3,-1) so on and so forth $\endgroup$ – Carson Sep 23 '14 at 19:22
  • $\begingroup$ Thank you. That's much better. $\endgroup$ – Carson Sep 24 '14 at 15:21

Hint: Try extended Euclide algorithm and Bézout coefficients.

  • $\begingroup$ right I understand this but i do not understand how this goes into predicting based upon a given difference n. I understand the idea of getting a single pair from the extended algorithm but I am personally more interested in the side about the patterns occur in these differences $\endgroup$ – Carson Sep 23 '14 at 19:41

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.