How large the limit it need to calculate the answer using Extended Euclidean algorithm

Revision en1, by OtterZ, 2025-04-27 09:45:53

Extended Euclidean algorithm is well-known for solving Diophantine Equation.But I found sometimes it makes integers out of bound and get wrong.Is there a way to proof that such algorithm bounds the integers in a proper limitations based on how large the absolute value of the given integers are.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English OtterZ 2025-09-10 10:35:17 3208 (published)
en8 English OtterZ 2025-07-22 06:54:16 12
en7 English OtterZ 2025-07-22 06:52:34 326
en6 English OtterZ 2025-07-22 05:08:39 1 Tiny change: '{C}\rfloor' -> '{C}\rfloor$'
en5 English OtterZ 2025-07-22 05:08:30 98
en4 English OtterZ 2025-07-21 17:04:58 250 Tiny change: ' + B}{C}]} in $\oper' -> ' + B}{C}]}$ in $\oper'
en3 English OtterZ 2025-07-21 16:50:53 407
en2 English OtterZ 2025-04-27 09:47:44 0 (saved to drafts)
en1 English OtterZ 2025-04-27 09:45:53 381 Initial revision (published)