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.

0
votes
0answers
21 views

linear equation with floating constants

I am to know the solution of equations like: 5.5*x + 1.33*y = 125(124.99 will also do), in which x and y are positive integers.. I tried extended Euclidean ...
-1
votes
3answers
35 views

Why is the GCD of two polynomials = 1, using the Euclidean Algorithm, if the last non-zero remainder is constant? [duplicate]

In this example the last non zero remainder is 15, however the solution is that the GCD is 1. Why is this the case, I tried searching for other such examples but I could not find an answer?
0
votes
3answers
43 views

How to calculate $\varphi(103)$?

How to calculate $\varphi(103)$? I know the answer is $102$ by looking at Wiki. But how can I find the multiplication of the prime numbers in order to use Euler's formula?
2
votes
3answers
63 views

Solving nonlinear Diophantine equations with Euclid's Lemma

How do I use Euclid's Lemma to solve the Diophantine equation $x^2 \equiv 13$ mod $17$? From there, how do I solve the Diophantine equation $s^2 \equiv 13$ mod $289$? Thanks in advance for any help.
0
votes
2answers
38 views

How does the Euclidean Algorithm apply on exponents m and n to show that $gcd(p^m-1, p^n-1) = p^{gcd(m,n)}-1$

No, this is not a duplicate of any thread. In fact, it is about a thread that I am still struggling to understand after all this time. I cannot comment on the thread because it was posted a very long ...
0
votes
1answer
27 views

How to solve equations using big $\Theta$

How would I prove that the statement $$10n^3 +3n = \Theta(n^3)$$ is true/false?
0
votes
1answer
50 views

how to work out a computer program running time

I have a question and im not sure how to tackle it.... algorithms have running times proportional to the following functions of the input size, denoted N: $N^2$ $2^N$ In one minute of computing ...
0
votes
1answer
51 views

Found $x^8$ while calculating inverse of $(x^6+1)$ in finite field $GF(2^8)$. Help???

So I was running the EEA (Extended Euclidean Algorithm) to find the multiplicative inverse of $(x^6+1)$ in the finite field $GF(2^8)$. Everything was going fine until the second last iteration where I ...
2
votes
3answers
52 views

Help proving polynomials division algorithm in $R[x]$ where $R$ is a domain.

Let $f(x), g(x) \in R[x]$ where $R$ is a domain, if the leading coefficient in $f(x)$ is a unit in $R$ then the division algorithm gives a quotient $q(x)$ and a remainder $r(x)$ after dividing $g(x)$ ...
1
vote
1answer
31 views

What can be said about the prime decomposition of the Bezout coefficients $\beta(a,b)$?

Let $a, b$ be coprime rational integers. Then by Bezout's lemma we can find $(s,t) := \beta(a,b) \in \mathbb{Z}^2$ such that $a*s + b*t = 1$. My question concerns the prime factorization of the ...
-1
votes
1answer
56 views

Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$ [closed]

How do you use the Euclidean Algorithm to solve the following: Find all pairs of positive integers $(x, y)$ for which $261x + 48y = 7881$
3
votes
1answer
79 views

GCD Euclid's algorithm as solution to the 2-buckets water puzzle

I completed an exercise on HackerRank, a site for programming exercises. The problem has been inspired from Die Hard 3 movie. The original problem is like the following. The problem You are given ...
2
votes
1answer
50 views

How can I use the relationship between the Fibonacci numbers and the EA to fill squares?

For this first question, I know how to apply the Euclidean algorithm and if I do, I get that the gcd is 1. I found this theorem online, thinking it might be able to piece together the relationship ...
1
vote
0answers
15 views

Remainders of Euclid's algorithm

Let $b_0,b_1,b_2$,... be the successive remainders computed in the course of Euclid’s algorithm. Prove that $b_{i+2} < b_{i}/2$ for any i ≥ 1. So we know that $b_i > b_{i+1} > b_{i+2}$ for ...
2
votes
1answer
47 views

Factoring a large semi-prime number.

Say I want to factor $N=12193263122374638001$ into prime factors. Surely this can easily be done with a computer and the answer would be $N=123456789\cdot9876543211.$ But If I want to do this by hand,...
0
votes
1answer
28 views

Euclidean algorithm in Euclid's words

When describing the Euclidean algorithm in his book, Elements, Euclid says the following: When the less of the numbers $a$ and $b$ is continually subtracted from the greater, some number is left ...
0
votes
2answers
34 views

how to solve 2x=4 in $Z_{12}$

How do I solve 2x=4 in $Z_{12}$ I know the $gcd(2,12) = 2$ and $2|4$ therefore there are 2 solutions, but I'm not sure how to solve this. I tried using the euclidean algorithm but it doesn't seem to ...
1
vote
2answers
34 views

GCDs for the polynomial ring over a Galois field.

You can find many examples of computing the inverse of an element inside a Galois field. (For example here) What happens if we look at the polynomial ring over a Galois field and would like to ...
2
votes
4answers
76 views

What are $x$ and $y$ in $xF_n$ + $yF_{n-1}$ = $1$?

We know that the $\gcd$ of consecutive Fibonacci numbers is $1$. But while finding the coefficients $x$ and $y$ in using euclidean algorithm in reverse direction I am not able to find any pattern so ...
0
votes
0answers
31 views

Find a min-pair-sum in sorted set greater then $u$ in sub-linear time

The 3-sum problem asks if a given set $S$ of $n$ real numbers contains three elements that sum to zero. I came to an interesting algorithm for solving it, but it created a different problem for me as ...
0
votes
1answer
23 views

3Sum complexity

I came up with a solution to the 3-sum problem, but I need your help to understand the complexity of my algorithm. I store the input in $n$ digits array. My goal is to find $a >= b >= c$ that ...
-2
votes
2answers
41 views

What is the remainder of Euclidean division of L=111…1 (2018 times) in base 7 by 9 [closed]

What is the remainder of Euclidean division of L=11111...1 (2018 times) in base 7 by 9?
0
votes
1answer
20 views

Finding the $\gcd$ of $a(x)$ and $b(x)$ in field $\mathbb{F}$

I'm trying to find the $\gcd$ of $a(x) = x^4 + 2x^3+x^2+4x+2$ and $b(x)=x^2+3x+1$ over $\mathbb{F_5}$. I've already tried Euclid's algorithm: $x^4 + 2x^3+x^2+4x+2 = x^2(x^2+3x+1) - x^3+4x+2$. Now I ...
1
vote
0answers
10 views

Polynomial reduction on algebraic curve

Consider two polynomial functions $f(x,y)$ and $g(x,y)$. I would like to find the restriction of $f$ onto the algebraic curve $g(x,y)=0$. My idea was to write a sort of Euclid algorithm $$ f(x,y) = ...
0
votes
2answers
17 views

Speed up divisors' calculation by hand

An exercise such the following one has to be solved by hand during an exam. So, knowing that I need to solve it in about ten minutes, I would like to know if there is a rapid technique to do it. ...
1
vote
0answers
28 views

Determine the quotient and the remainder of the division:

Determine the quotient and the remainder of the division: ($1$).of $f\in \mathbb K[x]$ by $x^2-a$ in $\mathbb K[x],$Where $\mathbb K$ is a field. ($2$).of $x^m-1$ by $x^n-1$ in $\mathbb Z[...
0
votes
2answers
56 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
15 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
26 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
20 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
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 + ...
4
votes
2answers
316 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 ...
1
vote
0answers
58 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
63 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
34 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
74 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
29 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
39 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
25 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
15 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
52 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
110 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
35 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
41 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
76 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
23 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
53 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
68 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$....