Giải thuật Euclid mở rộng được sử dụng để giải một phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) có dạngTrong đó a , b , c {\displaystyle a,b,c} là các hệ số nguyên, x , y {\displaystyle x,y} là các ẩn nhận giá trị nguyên. Điều kiện cần và đủ để phương trình này có nghiệm (nguyên) là U C L N ( a , b ) {\displaystyle UCLN(a,b)} là ước của c {\displaystyle c} . Khẳng định này dựa trên một mệnh đề sau:Nếu d = U C L N ( a , b ) {\displaystyle d=UCLN(a,b)} thì tồn tại các số nguyên x , y {\displaystyle x,y} sao cho a x + b y = d {\displaystyle ax+by=d}