3. Let g be the greatest common factor of 2,637,110,736 and b 2,961,110,016. ) F

Question

3. Let g be the greatest common factor of 2,637,110,736 and b 2,961,110,016. ) FindlisigEuclid's algorithm (B and to satisf the equation using one of the techniques shown in lectures, find suitable integers a and g = 2,961, 110,016 2637, 110.736 y (c) Check whether 6768 is a multiple of g. (It should be!) Find integers s and t such that 527,760 2,961,110,016 s 2,637,110,736 t. Don't just give a single s and t, but find all pairs of integers (s,t) that satisfy this equation. (d) As part of your answer to part (c) you should check that the numbers you have found do indeed satisfy the given equation. If you haven't done so, then do it here, as if a separate task. Explain any difficulties you encountered while doing such a check, and how you overcame them.

Explanation / Answer

Hi,
Euclids algorithm works as follows
gcd(a,b)
if (a == 0) return b;
else gcd(b%a, a);

so, we repeatedly take b%a until we make it 0, hence the iterations go like

Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.