# Questions tagged [euclidean-algorithm]

For questions about the uses of the Euclidean algorithm, Extended Euclidean algorithm, and related algorithms in integers, polynomials, or general Euclidean domains. This is **not** about Euclidean geometry.

45 questions
22k views

### How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
5k views

### Linear diophantine equation $100x - 23y = -19$

I need help with this equation: $$100x - 23y = -19.$$ When I plug this into Wolfram|Alpha, one of the integer solutions is $x = 23n + 12$ where $n$ is a subset of all the integers, but I can't seem ...
1k views

61 views

### Name for this Algorithm

I've managed to prove a bunch of properties about this algorithm that I came up with. I'm now curious to know it's name to see what other people have done. Given a number in base b N_0 = b N_X + ...
524 views

When calculating the greatest common divisor of two integers $a$ and $b$ by using the Euclidean algorithm, call the remainders obtained during the process $r_1,r_2,r_3,\ldots$. Show that each nonzero ...
181 views

### Euclidean algorithm of two polynomials

I got stuck on this question: Find the monic gcd of $f(x)=x^5-6x^4+13x^3-11x^2+x+5$ and $g(x)=x^2-3x+2$. I worked through the Euclidean algorithm, first multiplying $g(x)$ with $x^3$ but then the ...
122 views

### Euclidean Algorithm help!

(A) Use the Euclidean Algorithm to find $\gcd (57, 139)$. (B) Use your work from part (a) to write your gcd as a linear combination of the two numbers. (C) Find the inverse of $57$ in $U(139)$. I ...
265 views

### Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have no ...
2k views

### Uniqueness, units of the Eisenstein Integers [closed]

Let $\zeta$ be the cube root of 1 given by $\zeta=\frac{-1}{2}+i\frac{\sqrt{3}}{2}$ and let $\mathbb{Z}[\zeta]=\{a+\zeta b: a, b\in \mathbb{Z}\}$, called the "Eisenstein integers". How prove the ...
### Show that if $\gcd(a, b)\mid c$, then the equation $ax + by = c$ has infinitely many integer solutions for $x$ and $y$.
Show that if $\gcd(a, b)\mid c$, then the equation $ax + by = c$ has infinitely many integer solutions for $x$ and $y$. I understand that if there is one, solution for $ax+by =c$, then there are ...