Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

10
votes
0answers
178 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all $...
5
votes
0answers
182 views

Can we characterize all infinite Euclidean domains having exactly one invertible element?

$\mathbb Z_2$ and $\mathbb Z_2[x]$ are two Euclidean domains having exactly one invertible element. My question is: Can we characterize all Euclidean domains $D$ having exactly one invertible ...
3
votes
0answers
297 views

Using Euclidean Algorithm to find GCD of polynomials in $\mathbb{Q}[x]$

I had to find the $\gcd$ of the following polynomials in $\mathbb{Q}[x]$ using the Euclidean algorithm, and I wanted to check that I had done so correctly, since my notes on the subject from class are ...
3
votes
0answers
50 views

Set closed under quotients and remainders

Suppose that an infinite set $S= {0,1,2,4,8,...}$ of integers written in monotonically increasing order (that is, all other members are integers greater than 8) has the property that Euclidean ...
3
votes
0answers
37 views

Is there something wrong in this proof of a factoring theorem?

In Murty and Esmonde's Problems in Algebraic Number Theory, a proof of the following theorem is given. Let $K$ be a finite degree extension of $\mathbb{Q}$, and $\mathcal{O}_K = \mathbb{Z}[\theta]$ ...
3
votes
0answers
80 views

Examples of nonstandard Euclidean functions on Euclidean domain

An integral domain $R$ is a Euclidean domain iff there exists a function $N: R\setminus\{0\} \rightarrow \mathbb{Z}$ such that If $a,b\in R$, then there exists $q\in R$ such that either $a=qb$ or $N(...
2
votes
0answers
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 ...
2
votes
0answers
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$, ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
25 views

How to make polynomial division agree with Euclidean division when the variable $X$ takes numerical values?

Consider two polynomials $A(X), B(X)$ both $\in \mathbb{Z}[X]$ such that $\deg (B) < \deg(A)$. And let us perform a long polynomial division of $A(X)$ over $B(X)$, $$A(X)=Q(X)B(X)+R(X)$$ $$Q(X)=\...
1
vote
0answers
9 views

Representing extended as a modula equation

I've recently being doing research on discrete arithmetic, brought about by a research in artificial intelligence algorithm that analyses data much more accurately as rounding of digits is eliminated ...
1
vote
0answers
15 views

Remainders of Euclid's algorithm

Let $b_0,b_1,b_2$,... be the successive remainders computed in the course of Euclid’s algorithm. Prove that $b_{i+2} < b_{i}/2$ for any i ≥ 1. So we know that $b_i > b_{i+1} > b_{i+2}$ for ...
1
vote
0answers
10 views

Polynomial reduction on algebraic curve

Consider two polynomial functions $f(x,y)$ and $g(x,y)$. I would like to find the restriction of $f$ onto the algebraic curve $g(x,y)=0$. My idea was to write a sort of Euclid algorithm $$ f(x,y) = ...
1
vote
0answers
29 views

Determine the quotient and the remainder of the division:

Determine the quotient and the remainder of the division: ($1$).of $f\in \mathbb K[x]$ by $x^2-a$ in $\mathbb K[x],$Where $\mathbb K$ is a field. ($2$).of $x^m-1$ by $x^n-1$ in $\mathbb Z[...
1
vote
0answers
20 views

Inverse of a element $A \in \mathbb{F}_{2^m}, A \neq 0$ using Almost Inverse Algorithm

I have been proposed in class to obtain the inverse of a given element in $\mathbb{Z}_2$ field with the Almost Inverse Algorithm (AIA). I do not understand very well how to obtain it since the result ...
1
vote
0answers
70 views

Linear combination using extended GCD

Trying out different implementations of the extended GCD, i found out that all of them return the same linear combination factors for $egcd(a,b)$ and $egcd(b,a)$. For example (with this algorithm) I ...
1
vote
0answers
26 views

Is there a “symmetric” way to use the Euclidean algorthm on $R[x,y]$ for a domain $R$?

Let $R$ be any integral domain, and $R[x,y]$ the ring of polynomials over $F$ in two variables. If we regard $R[x,y]$ as $\left(R[x]\right)[y]$, i.e. as polynomials in $y$ whose coefficients come ...
1
vote
0answers
36 views

Find a specific solution to a linear Diophantine equation

Prove that for any given integers $b > a \geq 1$ there exists an integer solution $u$, $w$ to $au - bw = \text{gcd}(a,b)$ with $0\leq u\leq b-1$ and $0\leq w \leq a-1$. This is supposedly a simple ...
1
vote
0answers
24 views

Extended GCD of two zero polynomials over finite field

Extended GCD of two polynomials $a$ and $b$ results in two polynomials $s$ and $t$ so that $as + bt = \text{gcd}(a, b)$. What convention makes most sense when both $a$ and $b$ are zero? I found that ...
1
vote
0answers
19 views

(x,y) = (m_1,n_1) is the least positive solution of bx-ay= 1 while performing euclidean algorithm

I was reading number theory book by John Stillwell and I am stuck somewhere. The symbolic Euclidean algorithm is used when solving linear Diophantine equations. Suppose that we run the ordinary ...
1
vote
0answers
48 views

Confused about multiplicative inverse of 11 in $\Bbb{Z}_{26}$?

Find the multiplicative inverse of 11 in $\Bbb{Z}_{26}$ I used Extended Euclidean Algorithm to solve this problem. By Euclidean Algorithm, $$ 26=11\times2+4\\ 11=4\times2+3\\ 4=3\times1+1\\ 3=1\...
1
vote
0answers
107 views

Continued Fraction of $ \frac{7 + 2 \sqrt{2}}{9 + \;\,\sqrt{2}}$ with coefficients in $\mathbb{Z}[\sqrt{2}]$

We can read from various sources that $\mathbb{Q}(\sqrt{2})$ has class number one, and that $\mathbb{Z}[\sqrt{2}]$ is a Euclidean domain. However, it also has a group of units: $\mathbb{Z}[\sqrt{2}]^\...
1
vote
0answers
29 views

What is the meaning of the notation “$j_1(x|a_i|\alpha_i)$”?

I'm reading Dehn's Algebraic Equations. On the second of these two pages: There is the notation "$j_1(x|a_i|\alpha_i)$", but I can't figure out what it is. I guess I understand the subject ...
1
vote
0answers
97 views

Interesting recurrence relation in the euclidean algorithm…!

I do know how the Euclidean algorithm works $(I=0,1,\cdots)$: $$r_{I-1}=p_{I+1}r_I+r_{I+1}\quad(0\leq r_{I+1}<r_I)$$ here, if we let $r_{J-1}=0$, we have $r_{J-2}=gcd(r_{-1},r_0)$ according to ...
1
vote
0answers
347 views

How many steps does Euclid's algorithm take with two polynomials?

Say we have two polynomials, $a(x)$ of degree $n$ and $b(x)$ of degree $m$, where $n > m$. Euclid's algorithm lets us compute the GCD of these two polynomials using Euclidean division (detailed at: ...
1
vote
0answers
67 views

Find two integers for which the Euclidean algorithm will take 6 steps?

How does one approach this? Is it just trial or is there a method to find this if asked to find such numbers for a particular number of steps.
1
vote
0answers
41 views

Extended Euclid for multiple equations?

I'm trying to solve a programming problem, a subpart of the solution is like bellow: X is a positive integer where $X = m_1A_1 + a_1 = m_2A_2 + a_2 = m_3A_3 + a_3 = m_4A_4 + a_4 = m_5A_5 + a_5 = ...
1
vote
0answers
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: ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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.$ ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
116 views

Solving the GCD m = 735, n =252

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$....
1
vote
0answers
54 views

Extended Euclidean and Bezout's

Given two numbers, $a_0 = 172, a_1 = 61$ Write the the extended Euclidean algorithm and Bezout’s coefficients $x_k$ and $y_k$, i.e. the numbers such that the following equation is satisfied: $x_k a_0 ...
1
vote
0answers
256 views

Diophantine linear Equation Gaussian Integers

We know that $ax+by=c$ with $gcd(a,b)=1$ could be solved over $\Bbb Z$. Supposing if $a,b,c\in\Bbb Z[i]$, is there an analogous framework to find $x,y\in\Bbb Z[i]$ (at least of minimum norms)?
0
votes
0answers
21 views

linear equation with floating constants

I am to know the solution of equations like: 5.5*x + 1.33*y = 125(124.99 will also do), in which x and y are positive integers.. I tried extended Euclidean ...
0
votes
0answers
38 views

Find a min-pair-sum in sorted set greater then $u$ in sub-linear time

The 3-sum problem asks if a given set $S$ of $n$ real numbers contains three elements that sum to zero. I came to an interesting algorithm for solving it, but it created a different problem for me as ...
0
votes
0answers
16 views

Signs in subresultant pseudo-remainder sequence

Subresultant pseudo-remainder sequence is way of computing remainder sequence of two polynomials in $\mathbb{Z}$ and keeping the size of coefficients relatively small, but the signs of the remainders ...
0
votes
0answers
21 views

Why does the Euclidean Algorithm on naturals a, b <= fib(n) have a steps <= (n-2)

I have heard that the worst case for the euclidian algorithm is in the case of Fibonacci numbers. Can this be proven, and can it be proven only n-2 divisions are required (where euclidian algorithm is ...
0
votes
0answers
15 views

Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm

For the following algorithm, $X\leftarrow \{(i, n - i) \mid i = 1, ..., n- 1\}$ while $\max_{(a, b)\in X}b > 0$ do $\quad X \leftarrow \{(|a - b|, \min\{a, b\})\mid(a, b) \in X\}$ ...
0
votes
0answers
41 views

how to find the number of steps in a euclidean algorithm? (soft question?)

I have two questions. There is this mathematica code which includes a list of the form {a,b, number} where each sublist gave the number of steps in the euclidean algorithm for numbers a and b. the ...
0
votes
0answers
20 views

Prove that every vector from $R(A)$ is picture of only one vector from $R(A^{T})$

Let matrix $A$ is a record of some linear transformation $A:U\to V$. Prove that every vector from $R(A)$ is picture of exactly one vector from $R(A^{T})$. Suppose the opposite, let $w\in R(A)$ is ...