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

475 questions
40 views

### Why does the long division method not work when trying to find GCD of 2 polynomials that have an actual GCD of 1? [duplicate]

I have written a program that calculates the GCD of 2 polynomials using long division (Euclid's algorithm/theorem). I am trying to find the GCD of x^2 - 3 and x + 5, which I already know is 1. ...
29 views

### Need help with the following query about euclidean algorithm

question 3 Can anyone help me out with question 3? I tried using euclidean algorithm and got $$18x+3y = 3x( \frac{6+y}{x} )$$ which are equal so does that mean that 3x is the gcd of question 3?
59 views

### How many marbles?

One dozen of big marbles and small marbles is 132 gram. If one big marbles is 3 gram heavier than one small marbles, then specify the possibilities of how many are the big marbles and the small ...
73 views

### Doubt in proof of Euclidean Algorithm

I got this text from https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf Is it necessary for the proof to suppose: "Now suppose $d$ is a common divisor of $b$ and $r$..." By showing that if ...
40 views

### How do I properly do back substitution and put equations into the form of Bezout's theorem after using the Euclidean Algorithm?

For some problems, even longer ones, I've been able to see the pattern and properly do back substitution to bring a series of equations I've derived using the Euclidean algorithm to the form of Bezout'...
29 views

### Euclidean Algorithm with modular powers

I have these two questions which go as: 1) Find $x \in \{0,1...16\}$ such that $x^{13}\equiv2\pmod{17}$ 2) Find $x \in \{0,1...22\}$ such that $x^{13}\equiv3\pmod{23}$ I was wondering what the best ...
32 views

### Solution to Diophantine equation $19991112x + 2803y = 33$

I already found that $gcd(19991112,2803)=1$ so it does have solution. But I don't know how to find the solution. Equation: Diophantine equation $19991112x + 2803y = 33$
32 views

### Pirate and Bags of Coin

A pirate captain has 63 bags of coin with the same amount of coin inside each of the bags. If he wants to divided the coins to his 23 henchman evenly, he has to add 7 more coins. How many coins inside ...
2k views

### Properly comparing two histograms

I need to implement a function (in Golang) to compare the similarity/distance of two histograms. The histograms were generated from two different images. I have searched on the internet and have found ...
36 views

### Prove that $\gcd(P, P')$ is an irreducible polynomial over $\Bbb R.$

Let $P(X)$ = $X^4 + 2X^3 + 3X^2 + 2X + 1$ Let $P'$ be the derivative of $P$. Factor $P$ as a product of irreducible polynomials over $\Bbb R$. Find all the real and complex roots of $P$. What are ...
25 views

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. ...
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[... 2answers 57 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 ... 0answers 16 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 ... 1answer 29 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 ... 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 ... 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 + ... 0answers 81 views ### Examples of nonstandard Euclidean functions on Euclidean domain An integral domain$R$is a Euclidean domain iff there exists a function$N: R\setminus\{0\} \rightarrow \mathbb{Z}$such that If$a,b\in R$, then there exists$q\in R$such that either$a=qb$or$N(...
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 ...