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.

121 questions
178 views

163 views

AP + BQ = 1 (Euclidean algorithm)

if P, Q ∈ K[X] with no roots in common, then there exist A, B ∈ K[X] such that AP + BQ = 1. It should be done with the Euclidean algorithm applied on P and Q but I don't know how to do that so that ...
78 views

Roots of polynomials in two variables

Let $f \in k[x,y]$, $k$ is a field of characteristic zero. Assume that $(a,b) \in k^2$ is a root of $f$, namely, $f((a,b))=0$. Is it true that $(x-a)(y-b)$ divides $f$, namely, $f=(x-a)(y-b)g$, ...
115 views

Showing that the integers localized at a prime, p, is a Euclidean Domain

I want to show that the integers localized at some prime natural number $p$: $$R=\Biggl\{\frac mn \in \Bbb Q ~\Bigg\vert~ m,n \in\Bbb Z,\ n\notin p\Bbb Z\Biggr\}$$ is a Euclidean Domain, but I can't ...
928 views

Bezout Coefficients produced by Extended Euclidean Algorithm for $a$ and $b$

I was trying the Extended Euclidean Algorithm on various pairs of numbers to find a logic on the Bezout Coefficients produced. But, I am confused about the nature of the coefficients. I found the GCD ...
175 views

Find the number that gives the max number of steps for the Euclidean Algorithm

I assume that $a$, $b$ are integers $a > b > 0$. $N(a,b)$ denotes the number of steps taken in the Euclidean Algorithm to find $\gcd(a,b)$, for example, $N(7,2) = 2$. $M(a)$ then denotes the ...
62 views

For what pairs of numbers does the norm function fail as a Euclidean function in $\mathbb{Z}[\sqrt{14}]$?

(By "norm" here I mean "absolute value of the norm)" Are their infinitely many such pairs or is it finite in the sense that its just a few primes that cause the problem (like in that other famous ...
25 views

29 views

98 views

How to use recursion in Maple

I was trying to write a procedure that would compute a simple linear equation using the Extended Euclidean Algorithm. I was thinking of a procedure like the following: ...
25 views

Messages synchronization algorithm

We have two infinitely repeating messages consisting of characters $a-z$. Each character takes a different amount of time units to transmit; $a=1, b=2, c=4, d=8,e=16 ...$, character | tells us current ...
45 views

Plotting average number of steps for Euclid's extended algorithm

I was given the following assignment by my Algorithms professor: Write a Python program that implements Euclid’s extended algorithm. Then perform the following experiment: run it on a random ...
354 views

Extended Euclidean algorithm for polynomials

I have to find the gcd of $x^3 + 1$ and $x^2 + 1$ in $Q[x]$. I found this to be $1$. However I also have to write the gcd as a combination of these polynomials, but I'm stuck at this. I think I have ...
48 views

How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography. I have done some exercises with integers number but I have two exercises in which appears algebric ...
86 views

Euclidean domain

Verify that $R=\{a+b\frac{1+i\sqrt{7}}{2}|a,b\in \mathbb{Z}\}$ is Euclidean Domain. Here I think it is a ED. I tried to take norm function $N(a+b\frac{1+i\sqrt{7}}{2})=(a+\frac{b}{2})^2+\frac74b^2.$ ...
499 views

Kruskal-clustering algorithm

Let U be a set of points from $R^3$ and d:RxR $\to$ $R_{\geq0}$ an euclidean distance. For every partition of U with k classes, ($S_1$,...$S_k$), we define a quality of it as the shortest distance ...
52 views

Algorithm detect simple curves using Voronoi diagram or Delaunay triangulation?

I wonder if there is algorithm/method to determine if closed (or even non closed) curve is simple or not, using the mathematics from the field of computational geometry? Especially I wonder if exist ...
80 views

Euclid's algorithm

If we begin to use a Sieve of Eratosthenes on the set of naturals from $1$ through $200$, eliminating all multiples of $2, 3, 5$ and $7$ how many composite numbers will remain? This is a question ...
348 views

Proving the Gaussian Integers are a Principal Ideal Domain

Is there a good way to show that the Gaussian integers are a Principal Ideal Domain without using the fact that they are a Euclidean Domain? It seems like a lot of extra structure to need to prove ...
I understand everything except the values in $s_i$ and $t_i$ how do we get those values??? Can anyone please elaborate. I have no idea what the formula is for calculating the values in $s_i$ and $t_i$....