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.

71
votes
4answers
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?
33
votes
8answers
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 ...
4
votes
2answers
1k views

Extended Euclidean Algorithm problem

I'm confused about how to do the extended algorithm. For example, here's the gcd part gcd(8000,7001) $$\begin{align}8000 &= 7001\cdot1 + 999\\ 7001&=999\cdot 7+8\\ 999&=8\cdot 124+7\\ 8&...
7
votes
2answers
4k views

The ring $\mathbb Z[\sqrt{-2}]= \{a+b\sqrt{-2} ; a\in \mathbb Z,b\in \mathbb Z \}$ has a Euclidean algorithm

I need to prove that the ring $\mathbb Z[\sqrt{-2}]= \{a+b\sqrt{-2} ; a\in \mathbb Z,b\in \mathbb Z \}$ has a Euclidean algorithm, and to decide whether there are infinitely many primes in this ring. ...
4
votes
1answer
234 views

Visualizing tuples $(a,b,x,y)$ of the extended Euclidean algorithm in a four-dimensional tesseract. Are there hidden symmetries?

I am trying to visualize the possible symmetries in the Euclidean four-dimensional space of the $4$-tuples of points $(a,b,x,y)$ generated by the extended Euclidean algorithm, where $ax+by=gcd(a,b)$. ...
3
votes
1answer
372 views

Localization Preserves Euclidean Domains

I'm wanting to prove that given a ring $A$ (by "ring" I mean a commutative ring with identity) and a multiplicative subset $S \subset A$: if $A$ is an Euclidean Domain, and $0 \notin S$ then $S^{-...
9
votes
1answer
4k views

How to show every field is a Euclidean Domain.

I'm having trouble proving this. This is what I have so far: Let $F$ be a field. Let $v(x) \rightarrow 1$ for all $x$ not equal to $0$. So if we let $x$ be in $F$ where $x$ not zero then we can ...
10
votes
1answer
425 views

Have I found an example of norm-Euclidean failure in $\mathbb Z [\sqrt{14}]$?

Based on the proof that $\mathcal O_{\mathbb Q (\sqrt{-19})}$ is not Euclidean because it lacks universal side divisors, I have convinced myself that $\mathbb Z [\sqrt{14}]$ is Euclidean because it ...
2
votes
3answers
263 views

Euclidean Algorithm - find $\gcd(172, 20)$ and solve $172a + 20b = 1000$.

I am revising for an exam and have just realised that the euclidean algorithm questions in past exams are much harder than in homeworks! So i need some help please. I have a question here, i already ...
4
votes
2answers
348 views

'Gauss's Algorithm' for computing modular fractions and inverses

There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the ...
2
votes
6answers
426 views

Is there a simpler way to find an inverse of a congruence?

In order to find an inverse of a congruence, do we have to go through Euclid’s algorithm and do back substitution? Here is an example to find an inverse of 9 modulo 23.
2
votes
2answers
1k views

Proving the number of iterations in the Euclidean algorithm

Let m and n be natural numbers. Suppose $ min(m, n) \leq 2^k $ for some natural number k. Show that the Euclidean algorithm needs at most $ 2k $ iterations to find the GCD of m and n. Basically I have ...
0
votes
5answers
126 views

Solving equation using Euclidean Algorithm?

Euclidean algorithm leverages multiplication and subtraction, which humans are fairly good at, to make fractions like 15996751/3870378 reducible. Also useful in scaling equations down to their ...
2
votes
3answers
127 views

$15x\equiv 20 \pmod{88}$ Euclid's algorithm

Use Euclid's algorithm to find a multiplicative inverse of 15 mod 88, hence solve the linear congruence $15x\equiv 20 \pmod{88}$ So far I have: $88=5\cdot15+13$ $15=1\cdot13+2$ Backwards ...
1
vote
1answer
76 views

General solution for a Diophantine equation with more than two variables

Consider the Diophantine equation $$k_0a+k_1b+k_2c+k_3d+\cdots=1$$ where $a,b,c,d,\cdots$ are variables and suppose that a solution obtained through the Euclidean Algorithm is $a_0,b_0,c_0,d_0,\cdots$....
0
votes
1answer
159 views

How do the Euclidean and extended Euclidean algorithms work?

One can use the extended Euclidean algorithm to calculate the modular multiplicative inverse of a number, as it will be in the form $a x + b y = 1$, and if you take mod $b$ of both sides you get the ...
0
votes
3answers
336 views

Highest common factor of two polynomials

I have $$f(x) = x^3-2x^2-5x+6,\quad g(x)=x^2-2x-3$$ Then $f(x) = x(x^2-2x-3) +(-2x+6)$ So $hcf(f(x),g(x))=hcf((x^2-2x-3),(-2x+6))$ $x^2-2x-3=(-\frac{1}{2}x-\frac{1}{2})(-2x+6)+0$ So $hcf(f(x),g(x)...
0
votes
1answer
62 views

$N(ab) \geq N(a)$ is not necessary for the ring to be euclidean [duplicate]

The definition of euclidean ring in my textbook is 1) $N(ab) \geq N(a)$ 2) Euclidean algorithm works. However there is a note that the first condition is not necessary. There is a hint that we can ...
0
votes
2answers
355 views

Bezout's Theorem

I have seen the proof of Bezout's theorem via the use of strong induction. \medskip The theorem states the following; Let $a$ and $b$ $\in \mathbb{Z}.$ Then there exists $m$, $n$ $\in \mathbb{Z}$ ...
0
votes
2answers
417 views

Extended Euclidean Algorithm, what is our answer?

I am learning Euclidean Algorithm and the Extended Euclidean Algorithm. The problem I have is: ...
-3
votes
2answers
781 views

Finding $d=\gcd(a,b)$; finding integers $m$ and $n$: $d=ma+nb$

Let $a=8316$ and $b=10920$ a) Find $d=\gcd(a,b)$. greatest common divisor of $a$ and $b$ b) Find integers $m$ and $n$ such that $d=ma+nb$ this is what i've tried so far. correct me if I'm wrong ...
15
votes
3answers
3k views

Why are Fibonacci numbers bad for Euclid's Algorithm and how to derive this upper bound on number of steps needed in general?

I want to ask two things. The first is why are consecutive Fibonacci numbers the worst case for Euclid's algorithm? I keep seeing people say it in passing and I understand that it's really bad, but ...
9
votes
3answers
203 views

What is $\frac{1}{1+\sqrt[3]{2}}$ in $\mathbb{Q}(\sqrt[3]{2})$?

Since $\mathbb{Q}(\sqrt[3]{2})$ is a field, any number $\neq 0$ has a reciprocal. How then to write $\frac{1}{1+\sqrt[3]{2}}$ as a number $a + b\sqrt[3]{2} + c\sqrt[3]{4}$ with fractions $a,b,c \in ...
3
votes
1answer
664 views

Show that the Euclidean Algorithm terminates in less than seven times the number of digits in $b$.

Let $b=r_o, r_1, r_2,\dots$ be the successive remainders in the Euclidean algorithm applied to $a$ and $b$. Show that after every two steps, the remainder is reduced by at least one half. In other ...
6
votes
1answer
310 views

GCD of two elements in $\mathbb Z \left[\frac{1 + \sqrt{-11}}{2}\right]$

I have to find $(3 + \sqrt{-11}, 2 + 4\sqrt{-11})$ in $\mathbb Z \left[\frac{1 + \sqrt{-11}}{2}\right]$. If $\mathbb Z \left[\frac{1 + \sqrt{-11}}{2}\right]$ is an Euclidean domain, the euclidean ...
5
votes
3answers
1k views

Euclidean Algorithm vs Factorization

Can someone give me an explanation targeted to a high school student as to why finding thegcd of two numbers is faster using the euclidean algorithm compared to using factorization, there should be no ...
8
votes
1answer
207 views

Generalisation of euclidean domains

Recently I wondered how dependent the definition of euclidean domains is of the co-domain of the norm-function. To be precise: Let's define a semi-euclidean domain as a domain $R$ together with a ...
3
votes
3answers
140 views

Information about Problem. Let $a_1,\cdots,a_n\in\mathbb{Z}$ with $\gcd(a_1,\cdots,a_n)=1$. Then there exists a $n\times n$ matrix $A$ …

I would like to find some information about the following propositions, and unfortunately I haven't been able to find any. Let $a_1,\dots,a_n\in\mathbb{Z}$ with $\gcd(a_1,\dots,a_n)=1$. Then there ...
2
votes
2answers
222 views

Use Euclid's algorithm to find the multiplicative inverse $11$ modulo $59$

I was wondering if this answer would be correct the multiplicative of $11$ modulo $59$ would be $5$ hence $5\cdot11 \equiv 4 \pmod{59}$. Is this correct?
2
votes
2answers
1k views

To show $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain, why suffices to show only the field norm $N(a+b\sqrt{-5})=a^2+5b^2$ doesn't work?

This picture is an example in Dummit and Foote's Abstract Algebra. It shows that $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain by showing that the field norm $N(a+b\sqrt{-5})=a^2+5b^2$ doesn't ...
1
vote
2answers
1k views

Euclidean algorithm to find inverse modulo

Find an inverse for $43$ modulo $600$ that lies between $1$ and $600$, i.e., find an integer $1 \leq t \leq 600$ such that $43 \cdot t \equiv 1 (\text{ mod } 600)$. The solution below states $600 = ...
0
votes
1answer
594 views

Using Extended Euclidean Algorithm to find multiplicative inverse

Having some trouble working my way back up the Extended Euclidean Algorithm. I'm trying to find the multiplicative inverse of $497^{-1} (mod 899)$. So I started working my way down first finding the ...
0
votes
1answer
57 views

Question on uniqueness in the proof used for the partial fraction algorithm

Partial fraction algorithm Let $\mathbb{F}$ be a field, and let $f(x)$, $a(x)$, $b(x)$ be polynomials in $\mathbb{F}[x]$ such that $a(x)$ and $b(x)$ are coprime and $\deg f < \deg a + \deg b$. ...
3
votes
0answers
298 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
2answers
153 views

Choosing two numbers $a,b,$ such that the Euclidean algorithm takes 10 steps

The question is to find $2$ integers $a$,$b$ $\in \mathbb{Z}$ for which when applying the Euclidean Algorithm for finding the $\gcd \left(a,b\right)$ precisely $10$ steps are required. This is what I ...
3
votes
3answers
241 views

finding units of $ \mathbb{Z} [ \sqrt[3]{3}] $

In order took for units of $ \mathbb{Z} [ \sqrt[3]{3}] $ I am using a generalized Euclidean algorithm on three numbers. If $x \leq y \leq z$ then : $$ (x,y,z) \to \text{ sort } ( x, y ,z -y ...
2
votes
1answer
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 + ...
1
vote
1answer
524 views

Proof about euclidean algorithm

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 ...
1
vote
1answer
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 ...
1
vote
5answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
3answers
624 views

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 ...
0
votes
1answer
1k views

Find the gcd of polynomials

This is for a modern algebra course. Find the greatest common divisor of each of the following pairs of $p(x)$ an $q(x)$ of polynomials. If $d(x)=gcd(p(x),q(x))$, find two polynomials $a(x)$ and $b(...
-1
votes
2answers
435 views

Using Pollards rho algorithm for logarithms

I have been reading about the Pollard's rho algorithm for logarithms on Wikipedia. I wanted to work out an example. I use $n = 16$ and $p=16$ in my working. (Not sure if this is correct) Further I ...