3) باستخدام خوارزمية إقليدس ، أوجد القاسم المشترك الأكبر ( 42823 ، 6409 )
42823=6×6409+4369
6409=1×4369+2040
4369=2×2040+289
2040=7×289+17.................(*)
289=17×17+0
إذاً (6409،42823)=17

اقتباس :

أوجد س و ص بحيث 6409 س + 42823 ص = 17

من(*)
17=2040-7×289
17=2040-7×(4369-2×2040)
17=15×2040-7×4369
17=15×(6409-1×4369)-7×4369
17=15×6409-22×4369
17=15×6409-22×(42823-6×6409)
17=6409×147+42823×-22
س=147 ,ص=-22