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 ...
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 ...
13
votes
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.
12
votes
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 ...
12
votes
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 ...
10
votes
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 ...
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 $...
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 ...
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 ...
8
votes
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 ...
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. ...
6
votes
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 ...
6
votes
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 ...
5
votes
3answers
1k views

How to find gcd of $(a,a^n)$

I'm trying to use the Euclidean Algorithm to find the gcd of $(a,a^n)$. I started out with: $a^n = a \cdot a^{n-1} + 0$ but now I'm stuck in an endless loop of $a = 0 \cdot 0 + a$ $0 = a \cdot 0 +...
5
votes
4answers
1k views

Definition of prime element in a Euclidean ring does not make sense. Herstein - Topics in Algebra

Herstein's Definition: In the Euclidean ring $R$, a nonunit $\pi$ is said to be a prime element of $R$ if whenever $\pi=ab$, where $a,b \in R$, then one of $a$ or $b$ is a unit in R. $\mathbb Q$ is a ...
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 ...
5
votes
4answers
122 views

Clarification on the proof for the Euclidean algorithm

Lemma: Let $m$ and $n$ be positive integers with $m \leq n$. If $r$ is the remainder of dividing $n$ by $m$, then $(n,m) = (m,r)$. The proof is given as follows: We have by the division algorithm ...
5
votes
3answers
2k views

Prove that Euclid's algorithm computes the GCD of any pair of nonnegative integers

I've been struggling with a basic exercise involving Euclid's algorithm and mathematical induction. Given the following definition of the Euclid's algorithm (in Java): ...
5
votes
2answers
76 views

How to proceed with Euclidean algorithm for finding greatest common divisor of two polynomials.

I am trying to find \begin{equation*} gcd(x^4-x^3-4x^2-x+5,x^2+x-2). \end{equation*} I have done the first step of long division and found. \begin{equation*} x^4-x^3-4x^2-x+5=(x^2-2x)(x^2+x-2)-5x+5 \...
5
votes
1answer
129 views

Are the ring of integers of the constructible numbers a Euclidean domain?

I suspect that since Euclid uses the Euclidean Algorithm to perform division on constructible numbers in Elements, the ring of integers of the constructible numbers are a Euclidean Domain, but I have ...
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 ...
4
votes
4answers
784 views

If two elements in a ED have the same Euclidean norm, are they associates?

Is it obvious that in a Euclidean Domain two elements $x$ and $y$ having the same Euclidean norm are associates? Can someone give me a proof of this?
4
votes
3answers
193 views

Find $\operatorname{lcm}(2n-1,2n+1)$

I'm trying to find the formula for $\operatorname{lcm}(2n-1,2n+1)$ with $n \in \mathbb{Z}$. Here is my solution but I'm not sure about it. We know that $$\operatorname{lcm}(a,b)=\frac{\lvert ab \lvert}...
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&...
4
votes
3answers
778 views

A lot of confusion in the “Polynomial Remainder Theorem”?

Lately I've been reading about Polynomial Remainder Theorem from various sources, mainly from the wikipedea article, this post and some high school books. Wikipedea says that if we divide a polynomial ...
4
votes
10answers
430 views

Why does the largest $x$ such that $a$, $b$ divided by $x$ leave the same remainder equal $a-b$?

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$. It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I ...
4
votes
3answers
107 views

Number of integers satisfying $\left[\frac{x}{100}\left[\frac{x}{100}\right]\right]=5$

Find Number of integers satisfying $$\left[\frac{x}{100}\left[\frac{x}{100}\right]\right]=5$$ where $[.]$ is Floor function. I assumed $$x=100q+r$$ where $0 \le r \le 99$ Then we have $$\left[\...
4
votes
4answers
159 views

Suppose the integers $m^2$ and $n$ are relatively prime. Show that $m$ and $n^2$ are relatively prime.

My attempt so far: Since $m^2$ and $n$ are relatively prime, $am^2 + bn = 1$ for some integers $a$ and $b$. I know that I will have to use this to somehow prove that $cm + dn^2 = 1$ for some ...
4
votes
2answers
204 views

Solve $23x \equiv 1 \mod 120$ using Euclidean Algorithm

I want to do inverse modulo to solve the equation $$23x \equiv 1 \mod 120$$ And to do that I used the extended Euclidean Algorithm. $$120=23\times5+5$$ $$23=5 \times4+3$$ $$5=3\times1+2$$ $$3=2\...
4
votes
1answer
38 views

Expression for the element $(a+u)^{-1}$ in the extension field $G = F(u)$, where $u$ is a root of $x^{2}+px +q$ over a field $F$

Let $f = x^{2}+px+q$ be an irreducible polynomial over a field $F$ and let $G = F(u)$ be the extension of $F$ by a root $u$ of $f$. Every element of $G$ can be written in the normal form $a+bu$ where $...
4
votes
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 ...
4
votes
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 ...
4
votes
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? ...
4
votes
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 ...
4
votes
2answers
40 views

Diophantine Equation - least values for n : absolute values

Find all solutions to the diophantine equation $323x + 278y = 7$ Choose also a solution for which $|x| + |y|$ is as small as possible. My approach to this is to do the usual euclidean algorithm $...
4
votes
3answers
71 views

Can we prove the converse of the division algorithm?

The Division Alogrithm states that $\forall a, b \in \mathbb{N}$ where $b \neq 0, \exists q,r\in \mathbb{N}$ such that $a=qb+r$ with $0 \leq r \lt b$. I want to check whether it is true that $ \...
4
votes
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... ?
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
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 ...
3
votes
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 ...
3
votes
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$$...
3
votes
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 ...
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 ...
3
votes
3answers
63 views

$\mathrm{gcd}(n,n+2)=2$

I have a question: For what positive integers $n$ is $\mathrm{gcd}(n,n+2)=2$. Prove your claim. Is this correct?: If $n$ is odd then both $n$ and $n+2$ are odd so the gcd cannot be $2$. So assume ...
3
votes
1answer
462 views

Solving congruence $x^{37}\equiv3\mod527$

I came across this exercise in solving a modular congruence: Find an integer $0\le x<527$ such that $$x^{37}\equiv3\mod527$$ but being fairly new to this branch of number theory (and the topic ...
3
votes
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*...
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^{-...
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 ...
3
votes
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-...