Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
2answers
47 views

Euclidean division? ( $16=5\cdot 3+1$ vs $16=3\cdot 5+1$)

Is the equality $16=5\cdot 3+1$ the euclidean division of $16$ by $3$ or not ? This question is a point of discord between teachers where some them state that the divisor must be written in the first ...
0
votes
0answers
13 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 ...
2
votes
1answer
20 views

Finding all natural number solution(s) to linear Diophantine equation of three variables

Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end. For those curious, this puzzle comes from the game West of Loathing. It's ...
1
vote
0answers
17 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 ...
2
votes
1answer
56 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
0answers
35 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 ...
3
votes
1answer
57 views

Representation of an integer / Euclidean algorithm

Let $r \in \mathbb{N}$ be a natural number. Let $$L \geq 2(r-1)²$$ A paper (on quantum information theory, I'm not an expert in number theory or so...) I'm recently reading now says "One can easily ...
0
votes
1answer
25 views

Predicting the change in the denominator of a continued fraction when reversing the order of $a_1$ through $a_n$.

When reversing the order of $a_1$ through $a_n$ in a continued/extended fraction, (ie. [$a_1$: $a_2$, ... $a_{n-1}$, $a_n$] becomes [$a_n$: $a_{n-1}$, ... $a_2$, $a_1$]) we see that the denominator ...
1
vote
0answers
25 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 ...
0
votes
3answers
53 views

How to solve the equation $15x- 16y= 10$ [duplicate]

I am trying to find an $x$ and $y$ that solve the equation $15x - 16y = 10$, usually in this type of question I would use Euclidean Algorithm to find an $x$ and $y$ but it doesn't seem to work for ...
0
votes
3answers
26 views

How to solve this equation for d [closed]

Solve 17d mod 24 = 1. Would it be d = 17 inverse mod 24 and then solved using EEA?
0
votes
1answer
22 views

Finding alternative solutions to Bezout's Identity

Here's question I'm really struggling with: So far I believe I have found $d=21$ and $x=-2$ and $y=5$. From here I'm unsure where to go as part b is making very little sense, could someone explain a ...
1
vote
2answers
22 views

Bezout's identity on $F[x]$ with constraints

I have some issues with solving this exercise: Prove: Let $F$ be a field. If $f,g∈F[x]$ are relatively prime and not both constant, then there exists $a,b∈F[x]$ such that $af+bg=1$ and $\deg(a)<\...
0
votes
0answers
13 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 ...
1
vote
1answer
37 views

Computational Complexity of Euclidean Algorithm for Polynomials

Let us assume that the two polynomials that we have are degree $n$ polynomials. The naive Euclidean Algorithm for univariate polynomial does $O(n)$ divisions and each division takes $O(n^2)$. So ...
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\}$ ...
1
vote
1answer
48 views

Number of steps of Euclidean algorithm. why $r_i{_+}_2 < \frac{1}{2}r_i$?

I'm reading "Friendly Introduction to Number Theory". Now I'm working on Number of steps of Euclidean algorithm Exercises 5.3 on P35. 5.3. Let b = r0, r1, r2, . . . be the successive remainders in ...
1
vote
0answers
34 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 ...
0
votes
0answers
32 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 ...
2
votes
3answers
62 views

Polynomial division problem- find the degree of the remainder

Let $r(x)$ be the remainder when the polynomial $x^{135}+x^{125}-x^{115}+x^5+1$ is divided by $x^3-x$. Then a. $r(x)$ is the zero polynomial b. $r(x)$ is a nonzero constant c. the degree of $r(x)$ is ...
1
vote
0answers
19 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 ...
2
votes
2answers
50 views

Why isn't $\gcd(x^2+3x+2,x^2+x)=(x+1)$? [duplicate]

Excuse me for the confusing title. I was asked to find $gcd(x^2+3x+2,x^2+x)$ What i did is i factorized both polynomials $x^2+x=(x+1)x$ $x^2+3x+2=(x+1)(x+2)$ So i expected the gcd to be $x+1$ But ...
1
vote
1answer
60 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$....
1
vote
1answer
54 views

Division on a real quadratic ring of integers.

I've seen that $\mathbb{Z}[\varphi ] = \mathcal{O}_{\mathbb{Q}_{\sqrt{5}}}$, where $\varphi$ is the golden ratio, is a Euclidean domain with norm $N(x + y\varphi ) = x^{2} + xy - y^{2}$. Given a ...
1
vote
0answers
29 views

Division algorithm proof for b=qa+r [closed]

Let $ b= qa + R_a[b]$ where $R_a[b]$ is the remainder when b divided by a. Prove: 1- $ R_a[b+c]= R_a[R_a[b] + R_a[c]] $ 2- $ R_a[bc] = R_a[R_a[b] R_a[c]] $
6
votes
1answer
74 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 ...
1
vote
1answer
27 views

Are there online Euclidean GCD calculators for Euclidean domains other than $\textbf Z$?

There is no shortage of online calculators that will compute the GCD of two integers from $\textbf Z$. For example, the one from Calculator Soup, it will even show you the steps (try it with two ...
13
votes
5answers
172 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.
0
votes
3answers
48 views

Solve $m \equiv 2014^{2014}\mod 17$ for the least positive value of $m$

Find the least positive value of $m$ so that $m \equiv 2014^{2014}\mod 17$. I did an euclidean algorithm between $2014$ and $17$, $$\begin{align} 2014 &= 118 × 17 + 8\\ 17 &= 2 × 8 + 1\\ 8 &...
4
votes
2answers
38 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 $...
3
votes
1answer
129 views

Need help with Euclidean Algorithm in $\mathbb{Z}[i]$

I'm trying to find the GCD of $(85,1+13i)$ and $(47-13i,53+56i)$. I've tried, but to no avail. I keep setting it up and trying to do it with the same mindset as if i'm doing polynomial division, is ...
1
vote
0answers
16 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 ...
0
votes
1answer
44 views

Finding the inverse of $\sum\limits_{i=0}^{49}u^i$ where $u$ is a complex root of $x^{50}-2$

Consider $p(x)=x^{50}-2\in\Bbb Q[x]$ and $u\in\Bbb C$ such that $p(u)=0\ \ $ ($u^{50}=2$) By Eisentsein $p(x)$ is irreducible. If we define $\mu:=1+u+...+u^{49}$ multiplying by $u$ gives $$u+u^2+......
0
votes
1answer
60 views

Finding the correct $x$ to $ax - by = 1$

I want to find the modular inverse of $5 \pmod {13}$ such that : $$ 5x - 13y = 1$$ I tried to use the Euclidean alogritm for the GCD and use the extension(Extended Euclidean Algorithm) to solve for x....
1
vote
0answers
40 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\...
0
votes
1answer
26 views

Organizing objects in a near-square pattern

I don't have any fixed constraints but just a general idea. This probably a well known problem too - yet I can't seem to find any literature on it. Given n identical 2D objects, what is an algorithm ...
1
vote
0answers
80 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
1answer
28 views

Solve the Following Congruences, or Explain Why They Have No Solution

I have the following problem: Solve the following congruences, or explain why they have no solution: (i) $28x \equiv 3 \pmod{67}$; (ii) $29x \equiv 3 \pmod{67}$. First, I was wondering ...
0
votes
0answers
19 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 ...
0
votes
2answers
33 views

Solving inverse of modulo

How can I solve for: $$5^{-1} \mod 3$$ ? I am having hard time to understand how it is solve so please make it easy for me how it works.
0
votes
1answer
26 views

Euclidean space and set $M\cap M^{\bot}$

If $M$ is subspace of some Euclidean space $E$ than set $M\cap M^{\bot}$ sometimes is empty, sometimes is not. I read in book that $M\cap M^{\bot}=\{0\}$ so it can not be sometime empty sometimes not,...
0
votes
1answer
61 views

Euclidean space and subspace

I have some question that I get for homework. Let $U$ and $W$ subspace of Euclidean space $E$. Then if $U$ is orthogonal on $W$, then $U^{\bot}$ is orthogonal on $W^{\bot}$. For second question I ...
1
vote
1answer
28 views

How to evaluate $f(x)$ at the point $(x^2 + ax + b) \in \text{Spec} \, \mathbb{R}[x] $?

Can someone help me evaluate functions $f(x) \in \mathbb{R}[x]$ at the points in $\text{Spec}\, \mathbb{R}[x]$ ? $(x-a) \in \text{Spec} \,\mathbb{R}[x]$ so I think we still have a point there... $(x^...
1
vote
0answers
41 views

Calculate $\gcd(c^a+1,c^b+1)$ [duplicate]

Given positive integers $a$, $b$ and $c$, I'd like to ask whether we may adopt some variant of the Euclidean algorithm to calculate $\gcd(c^a+1,c^b+1)$ fast?
1
vote
1answer
46 views

Prove ring of dyadic rationals is a Euclidean domain

This is a question from page 105, Vinberg - A course in Algebra: Prove that the ring $A$ of rational numbers of the form $ 2^{-n}m,~m \in \mathbb{Z},~n \in \mathbb{Z}_+ $, is a Euclidean domain. ...
0
votes
2answers
75 views

Remainder when $4^{2018}$ is divided by $29$ [duplicate]

Find the remainder after division when $4^{2018}$ is divided by $29$. My approach: we have $$4^{2018}=16^{1009}=-\left(1-17\right)^{1009}=-\left(\binom{1009}{0}-\binom{1009}{1}17+\binom{1009}{2}17^2+...
0
votes
2answers
60 views

Extended Euclidean Algorithm to find 2 POSITIVE Coefficients?

There's a problem I ran into that said: "At a certain casino, blue poker chips are worth 9 dollars and white poker chips are worth 14 dollars. How many chips can Hank buy to spend exactly 206 dollars?...
1
vote
0answers
28 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
votes
5answers
49 views

Doubt regarding the manipulation of Bézout's identity

I had learnt the Bézout's identity in which it stated that For nonzero integers $a$ and $b$, let $d$ be the greatest common divisor $d = gcd(a, b)$. Then there exists integers $x$ and $y$ such that $...
1
vote
6answers
120 views

How do I find the last two digits $2012^{2013}$? [duplicate]

How do I find the last two digits 20122013 My teacher said this was simple arithmetics(I still don't see how this is simple). I thought of using Congruence equation as 2012 is congruent to 2 mod 10.....