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.
802 questions
-3
votes
0
answers
59
views
Euclid's Labour [closed]
edit: projecteuler.net discourages sharing direct solutions for problems after 1-100, i just need some hints, then i can work up from there
problem 958 (Euclid's Labour) from projecteuler.net (...
- 1
8
votes
3
answers
291
views
Why is there no Euclidean Algorithm for the least common multiple (lcm)?
The greatest common divisor (gcd) of two integers $a$ and $b$ can be computed with the Euclidean Algorithm.
With the gcd known, one can compute the least common multiple (lcm) via the formula $\mathrm{...
- 741
1
vote
1
answer
75
views
Does Euclidean division extend ordinary division?
Let $A$ be a Euclidean domain, i.e. an integral domain together with a Euclidean degree function $\delta \colon A \setminus \{0\} \to \mathbb{N}$ such that for every $a, b \in A$, $b \neq 0$ there ...
- 761
1
vote
1
answer
135
views
Resultants on two polynomials on two variables
Assume everything known about resultant of two polynomials on one variable. Now suppose we are given polynomials $P(x,y)$ and $Q(x,y)$, aiming to find whether they have a non-constant common factor.
...
- 2,989
1
vote
0
answers
70
views
How do I check if I found all generators of the solution module of a linear homogeneous diophantine equation?
I have a linear diophtantine equation
$$28x + 30y + 31z=365$$
and want to find all its solutions. Using the Gauss-Euclid algorithm, I start with the matrix
$$\pmatrix{28 & 1 & 0 & 0 \\ 30 &...
- 1,506
1
vote
0
answers
81
views
Euclid algorithm proof (Undergraduate algebra - Lang)
I have a question about the proof Lang provided in "Undergraduate Algebra". First, he proves that given two integers $m,n, \ m > 0$, there exists other two integers $q,r, \ 0\le r < m$ ...
- 173
0
votes
1
answer
201
views
Generating Numbers with Euclidean Algorithm [closed]
I recently looked at the question Sequences with Difference Occurring and the answer. The accepted answer suggests that
Repeatedly take the absolute value of the difference of consecutive terms, and ...
- 573
0
votes
1
answer
133
views
Euclidean Algorithm Problem with non-match coefficient [duplicate]
If $a,b$ natural numbers and $\gcd(a,b)=1$, determine all value of $\gcd(2a+b,b^5-a^5)$
Can anyone help me, I'm trying to use Euclidean algorithm but its just stuck.
First,you can split $b^5-a^5=(b-a)(...
- 29
0
votes
0
answers
28
views
Let $w = \frac{1+\sqrt{-11}}{2}$ and let $R = \mathbb{Z}[w] = \{a + b w \mid a, b \in \mathbb{Z}\}$. Show that $R$ is a Euclidean domain. [duplicate]
Let $w = \frac{1+\sqrt{-11}}{2}$ and let $R = \mathbb{Z}[w] = \{a + b w \mid a, b \in \mathbb{Z}\}$. Show that $R$ is a Euclidean domain.
I used the norm function $\phi(a+bw)=a^2 + ab + 3b^2$ as my ...
- 83
1
vote
0
answers
48
views
Why can the resolvent be determined using the euclidian algorithm?
It is fairly common to define the resultant and the $i$-th subresultant as determinant of some matrix involving the sylvester matrix. I would like to avoid the sylvester matrix.
I wonder if it is not ...
- 163
1
vote
2
answers
112
views
Invariance of the resultant under change of polynomials
Wikipedia states that the resultant of two monic polynomials $a,b\in K[x]$ remains the same, if one replaces $b$ with $(b-qa)$, where $q\in K[x]$ is another polynomial:
$$\mathrm{res}(a,b) = \mathrm{...
- 163
10
votes
2
answers
310
views
Avoid unnecessary calculations when multiplying matrices if only need one element of resulting matrix
The Problem:
I need only the bottom left element of a product of matrices $(\bf{M_1}+\bf{I})(\bf{M_2}+\bf{I})\cdots(\bf{M_N}+\bf{I})$,
where $\bf{I}=\begin{pmatrix}
1 & 0\\
0 & 1\end{pmatrix}$,...
- 233
1
vote
0
answers
35
views
Is the expected length of a random VRP known? [closed]
I have some regular area (e.g. a rectangle or a square), and I have $N$ random points there. Further, I have $k$ agents to visit the random points. The aim is to minimise total costs. Is there any ...
0
votes
0
answers
52
views
Question about the proof of Euclidean algorithm.
Theorem
If $a = bq+r, \text{then gcd}(a,b)=\text{gcd}(b,r) ... \text{gcd}(r_{i-1},r_i) = \text{gcd}(r_i,0)=r_i$.
Proof:
Let $d$ be a common divisor of $a$ and $b: d|a, d|b \implies d|(a-bq)\implies d|...
- 13
0
votes
1
answer
86
views
What exactly does the extended Euclidean algorithm compute for polynomials over a commutative ring?
Let $f,g\in A[x]$ with $A$ a commutative ring. IIUC, the extended Euclidean algorithm computes a minimal degree element in the ideal $\langle f,g\rangle\vartriangleleft A[x]$ (alongside the Bézout ...
- 14.5k