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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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. ...
user avatar
0 votes
0 answers
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 ...
user avatar
-1 votes
0 answers
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 ...
user avatar
  • 177
0 votes
0 answers
45 views

Calculate a non trivial divider of a number

given that: $1683411^{2}=4\mod(2195689)$ calculate a non trivial divider of $2195689$ (without using calculator) My try: $$ 1683411^{2}=4\,mod(2195689) \\~\\ 1683411^{2}-4=0\,mod(2195689) \\~\\ (...
user avatar
  • 341
0 votes
1 answer
36 views

Bezout's identity: general solutions???

S O L V E D After using the Euclidean algorithm to find the greatest common divisor between $ a = r_{-1} $ and $ b = r_0 $ (see figure) I'm trying to express in a general way the solution (x and y) of ...
user avatar
  • 33
1 vote
1 answer
49 views

Explanation for the Euclid Extended Algorithm

Please this is how the code for the extended-euclid algorithm was implemented in the book Introduction to Algorithm (Chapter 31 page 937 EXTENDED-EUCLID(a,b) if b == 0 return (a,1,0) else (d_1,x_1,y_1)...
user avatar
  • 13
1 vote
1 answer
35 views

How to find errors in solving for RSA Algorithm?

I'm working on an assignment, where we are given the values of p, q, and e. I have p = 11, q = 67, and e = 373. I've calculated n = p * q = 737 and φ = (p-1) * (q-1) = 660. . I found a d such that e * ...
user avatar
-1 votes
0 answers
66 views

Method in Euclidean Algorithm

My question is as follows: Assume that $a \geqslant b \gt 0$, $a$ mod $b$ = $r$. Why not use $gcd(a,b)=gcd(a,r)$ to compute (I mean why people do not widely use $gcd(a.b)=gcd(a,r)$ to find gcd of two ...
user avatar
0 votes
1 answer
66 views

Using the extended euclidean algorithm to crack LFSR

Question I am having trouble cracking an LFSR using the Extended Euclidean Algorithm (EEA). The problem comes as follow, let say we have the following LFSR : ...
user avatar
0 votes
1 answer
25 views

Euclidian Algorithm: proof that $n_i < \frac{n_{i-2}}{2}\quad \forall i\geq 2$ [closed]

In the euclidian algorithm to find the greatest common denominator $\text{gcd}(n,m)$ of $n$ and $m$ ($m\leq n$) I want to prove the following: $n_i < \frac{n_{i-2}}{2}\quad \forall i\geq 2$ where $...
user avatar
0 votes
1 answer
21 views

Greatest common divisor: Euclidian Algorithm, missing proof step [duplicate]

I'm working through the Euclidian Algorithm to find the greatest common divisor of two integers $n,m$. However I'm stuck at a very trivial step before the algorithm is even presented: $n,m\in \mathbb{...
user avatar
0 votes
1 answer
42 views

Find a solution for 23x=5 (mod 60)

The topic is euclidean algorithm and GCD. This is a simple question, but I'm just stuck finding an inverse for 23 in $Z_{60}$. I performed the algorithm and proved that 23 and 60 are coprime, so there ...
user avatar
1 vote
1 answer
53 views

Question about proof of Lamé's theorem

I ran into a proof for Lamé's theorem that has confused me. The proof goes like this: Prove: P(b): The number of recursive calls made by the Euclid-GCD algorithm when run with inputs $a ≥ b$ with $b&...
user avatar
  • 51
1 vote
1 answer
51 views

Suppose m and n are relatively prime integers. Prove that $m^2$ and $n^2$ are also relatively prime.

I know that $am+bn=1$ for some integers $a$ and $b$. I know that I will have to use this to show that $cm^2 + dn^2 = 1$. I tried squaring both sides but I am left with the term $2ambn$ which doesn't ...
user avatar
0 votes
0 answers
16 views

Prove that any square integer can be rewritten as $3m$ or $3m +1$ using Euclid's Division Algorithm for some integer $m$

The question asks me to prove that the square of any positive integer can be wrwritten as $3m$ or $3m + 1$. For it makes sense for $3m$: let $x$ be any positive integer let $b$ be the quotient $$x = ...
user avatar
0 votes
0 answers
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 ...
user avatar
-1 votes
2 answers
67 views

How to prove that $\gcd(m,n) = xm+yn$? [duplicate]

I have just begun learning about algebraic structures and factorisation and have seen the following statement: Given that integers $m$ and $n$ are not both $0$. There exist integers $x,y$ such that $\...
user avatar
  • 69
1 vote
0 answers
33 views

Show that the ring $\mathbb{Z}[\sqrt 2]$ is a Euclidean ring.

Let $$\mathbb{Z}[\sqrt 2]=\{a+b\sqrt 2 \mid a, b \in \mathbb{Z}\}$$ of the real numbers $\mathbb{R}$. Since the set of real numbers $\mathbb{R}$ forms a ring, the subset $\mathbb{Z}[\sqrt 2]$ also ...
user avatar
  • 11
2 votes
0 answers
152 views

An unproven algorithm for generating continued fractions for square roots.

I found that the following algorithm works correctly for $N=1 \sim 1000$ although I haven't been able to prove it. If this is already known, please point it out. If not, please prove it. Algorithm ...
user avatar
  • 408
0 votes
0 answers
32 views

Help me to find Bezout's number for two polynomial .

$f(x)=2x^4+5x^3+6$ $g(x)=x^3+2x^2+5x+4$ I can find $gsd(f(x),g(x))=1$ in $Z_7[X]$ but can't solve right $gsd(f(x),g(x))=f(x)*u+g(x)*v$ because i can't get 1 when try solve left part of equation, i ...
user avatar
2 votes
1 answer
43 views

Gaussian numbers algorithmic operations.

I have been working with this idea For some time I am struggling for a particular case, but first I will give the idea of this. Let be $F=\mathbb{Q}[i]$ and let be $\alpha\in F$, therefore $\alpha=\...
user avatar
  • 653
1 vote
1 answer
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", ...
user avatar
  • 113
-1 votes
1 answer
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 ...
user avatar
  • 4,395
0 votes
1 answer
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 ...
user avatar
2 votes
1 answer
68 views

In calculating GCD in $\mathbb Z[i]$ does it matter if we switch $a$ and $b$?

I am trying to solve this problem: Find the generator of the ideal $(47 - 13i, 53 + 56i).$ I know that I should use Euclidean Algorithm but I am wondering if it matters if I divided $a = 47 - 13i$ by $...
user avatar
  • 1,163
1 vote
0 answers
62 views

In $\mathbb{F}_2[x]$ check the polynomial $x^7+x^4+x^2+x+1$ for multiple factors.

In $\mathbb{F}_2[x]$ check the polynomial $x^7+x^4+x^2+x+1$ for multiple factors. Let $f(x)=x^7+x^4+x^2+x+1$. Then $f'(x)=7x^6+4x^3+2x+1 = x^6+1$. Then using Euclid's algorithm I calculated $\gcd(f,f')...
user avatar
0 votes
0 answers
31 views

Using algebraic expressions to uniquely represent all pairs of coprime nonnegative integers

After a bit of experimentation, I thought of an interesting sequence of algebraic expressions defined recursively as follows: $F_0 = 0$ $F_1 = 1$ For all integer $n \geq 2$, $F_n = a_{n-2} F_{n-1} + ...
user avatar
0 votes
1 answer
63 views

Solving polynomial diophantine equation in $\mathbb{F}_3[X]$ [duplicate]

Question: In $\mathbb{F}_3[x]$ write, if possible, the polynomial $1$ in the form: $$f(x)p(x)+g(x)q(x)=1$$ Where $p(x)=x^3+x^2+x+2$ and $q(x)=x^3+2x^2+2$. This is a question from Concrete Introduction ...
user avatar
-2 votes
2 answers
58 views

Chinese Remainder Theorem when n values are not coprime? [duplicate]

$$ x\equiv 2 \mod 20 $$ $$ x\equiv 7 \mod 15 $$ setting $a \equiv b \mod n$ how would you approach this as the two $n$ values are not coprime? I've broken down the $ 7\bmod15 $ into $x\equiv 7\mod3$ ...
user avatar
0 votes
0 answers
60 views

Strange Variation on Euclid's Game

I came across some instructions for Euclid's Game which I don't think are correct: Euclid’s game starts with two unequal positive numbers on the board. Two players move in turn. On each move, a ...
user avatar
1 vote
1 answer
74 views

steps to solve this simple number theory question?

I'm trying to study Number theory on my own, I encountered this problem. I knew how to solve it. the problem is Let $a,b,c \in Z$ such that: $$a = b*c*q1 + r1$$ and $$a = b*q2 + r2 $$ and $$ q2 = c*q3 ...
user avatar
0 votes
1 answer
46 views

What to do if the Extended Euclidean Algorithm terminates in one step?

I am trying to solve the linear congruence $14x \equiv 1 \pmod{113}$. So I first find $\gcd(14, 113) = 1$. However this means that: $113 = 14(8) + 1$ There is only one step needed. If I don't have ...
user avatar
1 vote
1 answer
50 views

Comparison of size of two numbers given different iterations of Euclidean Algorithm

Suppose that we have two different numbers, $A, B$, and arbitrary numbers $c,d$. Of course, they're all integers. If we've found $\gcd(A,c)$ by using Euclidean Algorithm at $n$th iteration. Whereas, ...
user avatar
1 vote
1 answer
49 views

Finding the distance from main point (hub) to the closest point

I have a hub point and multiple subpoints as shown in below figure. How to find the closest point from main hub (P) if there are 1000 points? Is there a specific ...
user avatar
  • 111
0 votes
0 answers
72 views

Confusion regarding proof of $\mathbb Z[i]$ is an Euclidean domain.

Let $\mathbb Z[i]$ be the ring of Gaussian integers.Define $d(a+bi)=a^2+b^2$ .I want to show that $\mathbb Z[i]$ together with $d$ is a Euclidean domain.So we have to show that for $x,y\in \mathbb Z[i]...
user avatar
0 votes
0 answers
21 views

Given the expression $(a-b)/2*s + b*t = d$, consisting of integers, find an equivalent expression $ ax + by = d $ where $x$ and $ y$ are integers.

So we are given the expression, $$ (a-b)/2*s + b*t = d, $$ where $a,b,s$ are odd integers and $t$ is even an integer. Is there some way to rewrite this in the form $$ax + by = d?$$ Where $x$ and $y$ ...
user avatar
0 votes
2 answers
42 views

High school level proof for Euclid's GCD theorem

I have noticed that in various high school math books, there is no proof given for the Euclid's GCD property of: If $a \ge b$ then $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,a-b),$ where $a,b\in \mathbb N^*.$ ...
user avatar
  • 1,354
2 votes
1 answer
46 views

Rewriting the expression $sx + ty = d $ where $d$ is the gcd of $s$ and $t$,

I have, $$sx + ty = d,$$ where $s,x,t,y,d \in \mathbb{Z}$ and $d$ is the gcd of $x$ and $y$. Is there anyway I could perhaps find an another expression: $$s'x + t'y = d,$$ where $s'$ is even? This ...
user avatar
0 votes
0 answers
35 views

Using Euclidean Algorithm to find a solution for linear Diophantine equation

I am trying to find a solution to $823x + 4526y = 1$ using the Euclidean Algorithm. Here is what I have so far, but I am doing something wrong because the answers don't work. $823x\ +\ 4526y=1$ $4526\ ...
user avatar
  • 149
1 vote
0 answers
17 views

Is combination of squared Euclidean and normalized cosine distance follow Bregman-divergence?

I know that squared euclidean distance satisfy the property of Bregman-divergence. I wanted to do some experiments using combination of various distance metric. So I am curious to know if I add ...
user avatar
0 votes
0 answers
46 views

Intermediate coefficient of Euclidean algorithm

I want to evaluate the intermediate coefficient of Euclidean algorithm. Let $$ \begin{aligned} &r_0:=a,r_1:=b,r_{i+1}:=r_{i-1}\bmod r_i\\ &q_i:=\left\lfloor \frac {r_{i-1}}{r_i}\right\rfloor\\ ...
user avatar
  • 1,181
0 votes
2 answers
268 views

Get distance between point A and C when their distances with a common point B is known [closed]

Background: My plan is to get the overall euclidean distance matrix for all the vectors in N number of dataset. Each dataset is basically an array of n-dimensional points. For e.g: A dataset can be ...
user avatar
2 votes
2 answers
47 views

(Euclid's Algorithm) What does b←b-a and a←a-b mean?

In the diagram below, what do steps 4 and 6? Is it the same as ⇒ where if the right is true, the left is true as well? Diagram: https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/...
user avatar
0 votes
1 answer
57 views

Proof of Euclidian's algorithm for non-coprime numbers

This question is part of my assignment and I am really struggling with it. Let us now apply these steps to a more general situation. As before we will suppose that the Euclidean algorithm runs in $3$ ...
user avatar
1 vote
2 answers
195 views

Finding modular inverse of $x^4$ in $GF(2^5)\mod (x^5+x^2+1)$

I cannot spot where I am going wrong in this. I am using Extended Euclidean's algorithm here. $(x^5+x^2+1) = (x^4)(x) + (x^2+1)$ $(x^4) = (x^2+1)(x^2+1) + 1$ let $P(x)=x^4$ and $Q(x)=x^5+x^2+1$ $(x^5+...
user avatar
0 votes
2 answers
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) = ...
user avatar
2 votes
2 answers
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 ...
user avatar
  • 39
-1 votes
3 answers
127 views

gcd($4n$,$2n+1$) for $n \in N$ using Euclid's algorithm

Using the Euclid's algorithm, find the gcd($4n$,$2n+1$) for $n \in N$ and express it as a linear combination of $4n$ and $2n+1$. I started by testing different values for n: $n = 1$ $\rightarrow$ gcd($...
user avatar
  • 47
1 vote
0 answers
36 views

Formula at the End of Euclid's Extended Algorithm

SETUP: Henri Cohen gives the extended Euclid algorithm as follows: Given $a, b \in \mathbb{N},$ find $(u,v,d) \in \mathbb{Z}^2 \times \mathbb{N}$ s.t. $$au+bv = d$$ and $d = \text{g.c.d.}(a,b).$ The ...
user avatar
  • 435

1
2 3 4 5
15