# 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.

582 questions
Filter by
Sorted by
Tagged with
56 views

25 views

37 views

### Why must a Euclidean function map to $\mathbb{Z}^{\ge 0}$?

I'm not sure I get the motivation for a Euclidean function having to map to $\mathbb{Z}^{\ge 0}$. E.g. it would seem that $\mathbb{R}^{\ge 0}$ would be a natural choice for a ring of "polynomials" ...
43 views

### Find an upper bound for the number of iterations over the Euclidean algorithm

Let $1\leq y\leq x\leq 2020$ be natural numbers. Find an upper bound for the number of iterations over the Euclidean algorithm on $(x,y)$. I don't have any idea how to solve it. Is it possible to ...
48 views

29 views

### Prove that : $\text{gcd}\bigg(a+b, \frac{a^p+b^p}{a+b}\bigg)=1 \ \text{or} \ p$

If $p$ is an odd prime and $a,b$ are relatively prime integers, prove that : $$\text{gcd}\bigg(a+b, \frac{a^p+b^p}{a+b}\bigg)=1 \ \text{or} \ p$$ Since it's obligatory to show the attempts to avoid ...
74 views

### If $f(x)$ is a common factor of $g(x)$ and $h(x)$ find $f(x)$

Given that $f(x)$ is a common factor of $g(x)=x^4-3x^3+2x^2-3x+1$ and $h(x)=3x^4-9x^3+2x^2+3x-1$ find $f(x)$ I tried to factorised $g(x)$ but it doesn't have any rational roots as I've already tried ...