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

706 questions
Filter by
Sorted by
Tagged with
27 views

### Finding the tightest (smallest) triangle that fits all points

I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given ...
• 872
1 vote
47 views

### Showing that $\frac{21n+4}{14n+3}$ is irreducible for every natural number n.

I wanted to prove that the fraction is irreducible using induction and have written the following proof: Let's take $n=1$, then $\frac{21\cdot1+4}{14\cdot1+3}=\frac{24}{17}$ which is not divisible. ...
27 views

### Let $m$ and $n$ be positive integers such that $m = 24n + 51$. What is the largest possible value of the greatest common divisor of $2m$ and $3n$? [duplicate]

Let $m$ and $n$ be positive integers such that $m = 24n + 51$. What is the largest possible value of the greatest common divisor of $2m$ and $3n$? I'm trying to figure out how to use the Euclidean ...
40 views

### What is the fact Extended Euclidean Algorithm is based on? [duplicate]

I've started to wonder about something that should be easy enough to explain for one knowing the topic well enough, but I'm unable to derive that explanation. Euclidean Algorithm is based on a fact ...
• 177
45 views

30 views

### Extended gcd pseudocode

I need to implement extended Euclidian algortihm for polynomials to get coefficients of Bézout's identity. Problem is I'm struggling with correct implementation of such function. I've found some code ...
67 views

• 653
1 vote
64 views

### Inverse with Extended Euclidean Algorithm

I'm solving a task from https://www.coursera.org/learn/crypto/, particularly the following question: I know that 3x - 5 = 0 and since "ax + b = 0" that implies "x = -b * a^-1", ...
• 113
43 views

### Does Euclid's lemma for Euclidean Algorithm work for any integers $a,b,c,d$ such that $a=bq+d$? [duplicate]

I thought that lemma (*) was $\gcd(a,b) = \gcd(b,r)$ where $a=bq + r, \, 0≤r <b$, and it worked when you divide $a$ by $b$ to get the quotient $q$ and a remainder $0≤r<b$. But I don't think any ...
• 4,395
25 views

### Different methods for encoding 3D positions as single number?

The obvious one is modulation/multiplication of each axis by different pitch, or dedicating different bits for each axis (in computer terms) But are there known smarter methods? i.e. normalized ...
68 views

• 1,072
31 views

• 33
331 views

### Prove gcd(x,y) = gcd(x-y,y) for x > y [duplicate]

Prove gcd(x,y) = gcd(x-y,y) for x > y Here is my work so far: If gcd(x,y) = d, then we can denote x = ad , y = bd, so x - y = (ad - bd) = d(a - b), so (x-y) is a multiple of d, so gcd(x -y, y) = ...
• 145
169 views

### Find all of the possible solutions of $250x+111y=7$, where both $x$ and $y$ are integers.

This is my steps 1 = 28-1x27 = 28-1x(111-3x28) = 4x28-1x111 = 4x(250-2x111)-1x111 = 4x250-9x111 x7=> 7 = 28x250-63x111 Then I don’t know why the ...
• 39