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

475 questions
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?
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 ...
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 ...
5answers
209 views

### GCD in arbitrary domain

Is there a domain where computing GCD of two elements is not trivial (i.e. Euclid's algorithm will not work)? AFAIK we can always use the Euclid's algorithm in a Euclidean Domain.
3answers
940 views

### Finding consecutive naturals that all fail to have inverses modulo $70$

I'm not sure how to prove the following statement true or false. There exist five consecutive naturals that all fail to have inverses modulo $70$. I know I can apply the Euclidean algorithm to ...
1answer
141 views

### What other forms can Euclidean failure take?

I know that $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain. However, I'm still interested in trying to see how far the Euclidean algorithm can get. With some numbers, it can get all the way to the ...
1answer
424 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 ...
0answers
178 views

1answer
206 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 ...
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. ...
1answer
130 views

### What is the worst case for the Euclidean algorithm in $\mathbb Z[i]$?

As you know, the worst case for the Euclidean algorithm in $\mathbb Z$ is two consecutive Fibonacci numbers. As any online GCD calculator that shows the steps of the Euclidean algorithm will ...
1answer
306 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 ...
3answers
1k views

2answers
130 views

### Another real quadratic integer ring, Euclidean but not norm-Euclidean, with norm function needing only two adjustments?

I have come to know about $\mathcal O_K$ with $K = \mathbb Q(\sqrt{69})$. The norm function needs to be adjusted to absolute value, as is the case with other real rings, but it also needs to be ...
1answer
62 views

### Confusion for Proof of GCD Theorem?

I'm having some trouble understanding a part of a theorem that states that the gcd between two integers exists and is unique. First it state the Euclidean Algorithm for positive integers, that for ...
1answer
249 views

### Why do polynomials and integers both have a long division algorithm?

The grade-school long division algorithm and the polynomial long division algorithm are identical, if I'm not mistaken. Why is this the case? Are the two algebraic structures identical in some sense? ...
2answers
342 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 ...
2answers
40 views

2answers
950 views

### Prove the validity of gamma function equation $\Gamma(n)\Gamma(n+1/2) = 2^{1-2n}\sqrt{\pi}\;\Gamma(2n)$

How to prove this identity for natural $n$? $$\Gamma(n)\Gamma(n+1/2) = 2^{1-2n}\sqrt{\pi}\;\Gamma(2n)$$ Firstly, I set $n=1$ and looked at general gamma equation. How to simplify or... ?
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)$. ...
3answers
141 views

### Prove $373$ is prime when $\gcd(255255, 373) = 1$

I needed to find $\gcd(255255, 373)$ and then explain why that proves $373$ to be prime. I understand the first part, but not the prime part at all. Here is how I figured the first part out using ...
2answers
44 views

### Why can't the decimal fraction part of $\frac{1}{d}$, $d \in \mathbb{N}^\ast$ have a recurring cycle of length greater than $d$?

I am trying to solve problem 26 from project euler which asks Find the value of $d < 1000$ for which $1/d$ contains the longest recurring cycle in its decimal fraction part. I noticed that all the ...
3answers
765 views

### Euclidean Algorithm : Confusion with how many divisions needed?

The question asks how many the divisions required to find $\gcd(34,55)$. I did it using the Euclidean Algorithm with the following result. $$55=1 \cdot 34+21$$ $$34=1 \cdot 21+13$$ $$21=1 \cdot 13+8$$...
4answers
3k views

### Need help describing “extending modulo to decimal numbers”

I've recently written a paper outlining the algorithm for determining departure time, arrival time, and flight duration for air travel across multiple time zones, including crossing the International ...
3answers
241 views

1answer
2k views

### Find the inverse of $2$ modulo $17$ using the Euclidean algorithm

The question states "find the inverse of a modulo m for each of these pairs of relatively prime integers" ATTEMPT AT SOLUTION \begin{align*} 17 & = 2 \cdot 8 + 1\\ 2 & = 1 \cdot 2 \end{align*...
1answer
372 views

2answers
2k views

### RSA and extended euclidian algorithm

I'm learning about RSA, public private key stuff, and I just found a very nice article explaining the basics. http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-...