Abstract Algebra: Theory and Applications · Problem 2.5.3

Groups — Thomas Judson

Mathematics — Abstract Algebra · euclidean-algorithm-programming

Problem

Write a computer program that will implement the Euclidean algorithm. The program should accept two positive integers

a

and

b

as input and should output

\gcd(a,b)

as well as integers

r

and

s

such that

\gcd(a,b) = ra + sb.