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

464 questions
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 ...
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?
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?
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.
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 ...
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?
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 ...
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 ...
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)$ ...
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 ...
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$
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
10 views

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