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.
742
questions
0
votes
0
answers
49
views
Canonical unit multiples in $\Bbb Z/n\Bbb Z$
I'm writing code to do computation in algebraic number fields and am (re)-learning some algebra in the process.
When working with a ring, it seems useful to have an operation that "canonicalizes&...
- 8,466
6
votes
0
answers
75
views
Given $a$ in $\gcd(a,b)$ with $a > b > 0$, how can I find $b$ which give the maximum number of steps for the Euclidean algorithm?
Given $a$, where $a$ and $b$ are positive integers with $a > b$, how can I find the values for $b$ which give the maximum number of steps for the Euclidean algorithm $\gcd(a,b)$?
For example, where ...
- 161
0
votes
2
answers
31
views
Double-checking work on finding gcd with Euclidean algorithm
I'm still learning the Euclidean algorithm and am hoping that someone can check my work on this problem:
Find $gcd(1001, 11)$
$1001 = 91(11) + 0 = 90(11) + 11$
$gcd(1001, 11) = 11$
- 71
0
votes
1
answer
58
views
How do I find the cube root using the Extended Euclidean Algorithm? (RSA broadcast attack)
This is to solve for $m^3$ in an RSA broadcast attack where I have $c1$, $c2$, $c3$, $N1$, $N2$, $N3$ and $e=3$.
I use CRT (Chinese Remainder Theorem) to get $c1 \equiv c2 \equiv c3 \pmod {N_1 N_2 N_3}...
- 224
1
vote
1
answer
27
views
Computing a minimal sublattice containing two other sublattices, GCD of a lattice
I've been trying to read a paper regarding the analogue of a GCD for lattices, but I'm not sure I understand how to decipher this notion. This is given in Section 3.1 when the author discusses the '...
- 5,913
0
votes
1
answer
44
views
Multiplicative inverse in the extended euclidean algorithm
I am trying to use the extended euclidean algorithm to find the multiplicative inverse of 02 (in hexadecimal) and $x^8+x^4+x^3+x+1$ over GF($2^8$). I tried to apply the algorithm between $x^2$ and the ...
- 1,801
0
votes
0
answers
30
views
Can we use quotients in proving the correctness of the Euclidean algorithm?
The Euclidean algorithm, for finding the gcd of two number, let $a,b;$ changes in each successive step the dividend to be the previous step's divisor, and divisor to be the previous step's remainder.
...
- 4,480
0
votes
0
answers
75
views
Question on Tim Gowers's Unique Factorization Proof
In Tim Gower's blog post: How to discover a proof of the fundamental theorem of arithmetic. he gives a proof of Euclid's Lemma using Lagrange's Theorem, but at the end he links to an older post giving ...
- 35
-2
votes
0
answers
34
views
By using euclidean algorithm find gcd of 3645 and 2347. Also express gcd as linear combination of the given numbers [duplicate]
I was able to find the gcd pretty easily but I am facing alot of problems in the second part of the question.(edit : its done... there were just some stupid mistakes)
0
votes
0
answers
54
views
Show that the quadratic integer ring $\mathcal{O}=\{a+b\frac{1+\sqrt{-3}}{2}|a, b\in\mathbb{Z}\}$ is an Euclidean Domain.
The Problem: Let $F=\mathbb{Q}(\sqrt{-3})$ be a quadratic field with associated integer ring $\mathcal{O}=\mathbb{Z}[\omega]=\{a+b\omega\mid a, b\in\mathbb{Z}\}$ where $\omega=\frac{1+\sqrt{-3}}{2}$, ...
- 981
0
votes
2
answers
38
views
Alternative implementation of the Extended Euclidean Algorithm
I'm taking an "Algebra for Computer Science" course, and the professor briefly touched upon an implementation of the Extended Euclidean algorithm I can't seem to understand right now.
In ...
- 402
0
votes
0
answers
20
views
Montgomery algorithm and Extended Euclid algorithm [duplicate]
In this document http://koclab.cs.ucsb.edu/teaching/cs154/docx/Notes7-Montgomery.pdf on page 3 0.2 An Example of Exponentiation have a example for calculating r^-1 and n'
Where r * r^-1 − n * n' = 1 . ...
- 1
0
votes
1
answer
32
views
How can I convince myself that the steps in euclid's algoritm are valid?
I'm banging my head against Euclid's algorithm at the moment and I think I need some external input in order to gain a breakthrough....
Let's say we have a fraction like:
$$ \frac{216}{66}=3*66+18 $$
...
- 691
-1
votes
1
answer
38
views
Proof that euclidean algorithm terminates for each input
As for my discrete math exam preparation our lecturer gave us a list of statements which we have to know how to proof in case if we have it in our test list. But I have some problems with this one The ...
- 1
-1
votes
1
answer
29
views
Correct method for finding the multiplicative inverse of an element in $\mathbb{Z}/n\mathbb{Z}$ [duplicate]
I have found two different methods for finding the multiplicative inverse of a number modulo $n$ in $\mathbb{Z}/n\mathbb{Z}$.
One is using the Extended Euclidean Algorithm, which produces a different ...
-1
votes
4
answers
68
views
Given that $gcd(1,4) = 1$, how can I apply the Euclidean algorithm to find values for $x$ and $y$ such that $1x + 4y = 1$?
An intermediate step in a problem I'm trying to solve is to find $gcd(1, 4)$. Using the Euclidean algorithm, this is $1$:
$$
1 = 0\times4 + 1 \\
4 = 4\times1 + 0
$$
Bezout's identity tells us that the ...
- 2,863
0
votes
1
answer
54
views
Prove that $\gcd(x,y)=\gcd(x,x+y)$ [duplicate]
I want to prove: $$\gcd(x,y)=\gcd(x,x+y)$$
I thought of using Euclid's algorithm, where $p=q*d+r$
My proof:
$\gcd(x,x+y)$ is equivalent to
$$ (1) x+y=x*1+y $$
The next step in the algorithm is:
$$x=d*...
0
votes
0
answers
59
views
polynomial remainder sequences of $x^n$ and a polynomial of degree $n-1$
Suppose you have polynomial $f$ of degree up to $n-1$ with $n-t$ distinct non-zero roots. So $f$ can be written as $f=g\cdot h$, where $g$ has degree exactly $n-t$ and it has exactly $n-t$ simple ...
- 41
0
votes
0
answers
10
views
Let $R$ a Euclidean domain and $m$ the minimum integer in the set of norms of non zero elements of $R$. Prove nonzero elements of norm $m$ are units [duplicate]
Let $R$ be a Euclidean domain and let $m$ be the mimimum norm on the set of nonzero elements of $R$. Prove every non-zero element of $R$ of norm $m$ is a unit.
Is it enough to take some $a \in R \...
- 2,981
0
votes
2
answers
92
views
Extended Euclidean Algorithm to find modular multiplicative inverse of polynomial in $\mathbb{Z}_m[X]/P(X)$ if m is not prime?
I'm looking into modular polynomial rings over the integers (if that's the right term?) i.e. $\mathbb{Z}_m[X]/P(X)$ where $\mathbb{Z}_m$ is the ring of integers modulo m, and P(X) is some polynomial ...
- 189
-1
votes
1
answer
78
views
Proof related to gcd of three numbers [duplicate]
We want to develop a version of the Euclid-Bézout algorithm for triples of natural numbers.
Let $n_1$, $n_2$, $n_3 \in \mathbb{N}$ but not all three zero. We define $\gcd(n_1, n_2, n_3) \in \mathbb{N}$...
- 1
0
votes
0
answers
13
views
Find sequence of point from $u$ to $v$ such that each is at distance $d(u,v) = t$ with $t \in [1,2]$.
The problem is the following:
Given $n$ points in $\mathbb{R^2}$, give an algorithm that given points $u$ and $v$, $u \neq v$ find a sequence of points such you can go from $u$ to $v$ and in each step ...
2
votes
0
answers
25
views
Proving that equivalence class has invertible element in residue class.
Let $z \in \mathbb{Z}$ a number with characteristic
$$
\exists x,y \in \mathbb{Z} \: 1 = xz + yn
$$
Show that $[z]_n$ in $(\mathbb{Z}_n, *)$ is invertibel. Figure out invertibel element also.
$* = $ ...
- 33
2
votes
0
answers
32
views
Extended Euclidean algorithm and extended remainder sequence
Consider the rational polynomials $h,f$:
$h:=x^8+x^6-3x^4-3x^3+8x^2+3x-5$
$f:=3x^6+5x^4-4x^2-9x+2$
Compute polynomials $r,t \in \mathbb{Q}[x]$ such that
$r\equiv tf \mod{h}$ with $\deg r < 4, \deg ...
-1
votes
1
answer
32
views
Euclidean Algorithm Lemma and Application [duplicate]
$(b)$ Suppose $ak+bl=1$. Prove that gcd($a,b$) = $1$.
$(c)$ Prove that gcd($6a+8,4a+5$)=$1$.
For ($b$) Let $h$ denote the highest common factor of $a$ and $b$. Hence $h$ divides $ak+bl$ by a lemma. If ...
- 969
1
vote
1
answer
45
views
Euclidean division of a linear combination of real numbers
I have this following problem:
$T=nP_1 + mP_2$
With $T$, $P_1$ and $P_2$ real numbers. I have access to those three values, but is it possible to determine $m$ and $n$ ? This looks like the Bézout ...
0
votes
1
answer
56
views
Efficiency Analysis of the Euclidean GCD algorithm
The question is, if the Euclidean algorithm is called with values $p$, and $q$ such that $p < q$. Then runtime of the Euclidean algorithm is upper bounded by $O(\log_{3/2}(p+q))$. How can this be ...
- 3
0
votes
1
answer
22
views
Using Extended Euclidean algorithm question
Suppose we have $f=x^5-1$ and $g=x^2-1$ and I have found the gcd using the Euclidean algorithm but I’m trying to find a way of expressing this in the way $$af+bg=1$$ where $f, g \in Q[x] $. I know ...
- 1,950
1
vote
0
answers
34
views
Using number theory for a particular case to achieve strong induction generalisation [duplicate]
So I was looking at a few strong induction problems such as the following "Given an unlimited supply of 5 cent and 7 cent stamps, what postages are possible?" and it seems the computation ...
- 37
1
vote
1
answer
95
views
Use the Euclidean algorithm to show that 15m + 7 and 2m + 1 are relatively prime
I am familiar with the Euclidean algorithm but I do not understand how to show that two numbers are relatively prime if there is an m
0
votes
1
answer
37
views
Simple upper bound on number of iterations of Euclidean algorithm
This is from the book "An Introduction to the Theory of Numbers" by Niven, Zuckerman and Montgomery.
The exact number of iterations $j$ of the Euclidean algorithm required to calculate $(b,...
- 3,432
0
votes
0
answers
38
views
Euclidean Division Lemma
I am doing this question regarding GCD and to complete my solution, I need to prove that for any two given natural numbers, say m and n, where n is odd, applying the euclidean division lemma ...
- 148
1
vote
1
answer
60
views
Proof that $x_i$ and $y_i$ are coprime in the extended euclidean algorithm
Let $b,c\in \mathbb{N}$ such that $b\gt c$. Let $r_{-1}=b$ and $r_0=c$. Then we define the numbers $q_i$ and $r_i$ as the quotient and remainder of euclidean division of $r_{i-2}$ and $r_{i-1}$, i.e. $...
- 137
1
vote
1
answer
68
views
Find $q,r$ if $q^2+r=2000$
Let $a,b \in \mathbb{N}$ such that when $a^2+b^2$ is divided by $a+b$, the quotient is $q$ and remainder is $r$ such that $q^2+r=2000$. Find $q,r$
My try:
Obviously $a \ne b$ for if we have $r=0$ $\...
- 12.5k
0
votes
1
answer
40
views
Proving that I can write $a(\geq 1$ in base $b(\geq 2)$
Question:
Suppose that $a\geq 1$ and $b\geq 2$. Show that there exist $a_0,a_1,...,a_d \in [0,b-1]$, such that
$a=a_d b^d+a_{d-1}b^{d-1}+....+a_0$
I tried to approach the problem using the Euclidean ...
- 137
2
votes
2
answers
108
views
Best strategy to find $x$
We have a machine where we can send numbers $a$ and $b$ where both are $>1$ and then the machine returns $gcd(a,x+b)$ where $x$ is the number we wish to discover. We have $25$ tries to get $x$ ...
0
votes
1
answer
67
views
Proving the validity of a more efficient algorithm than the extended euclidean algorithm for relative primes
I read in a book that there is a more efficient algorithm (which uses less storage in computers) than the extended euclidean algorithm in the case of relative primes.
As it appears in the attached ...
2
votes
2
answers
58
views
Algorithm to convert a real to surd representation?
Supposing I'm given an infinite-precision calculator containing a number $x$, which I know to be the ratio of two coprime integers $p$, $q$, with $q > 0$, and I want to find out what those integers ...
- 1,331
0
votes
1
answer
83
views
Euclid's algorithm for polynomials on MAGMA
I have to compute the GCD between two polynomials on MAGMA. I do not have any problem with the Euclidean Algorithm but I have a problem with the function "mod" that, as they say on the MAGMA ...
5
votes
3
answers
135
views
Let $a_1$ be linearly independent to $a_2$ over $\mathbb{Q}.$ For $n\geq 3,$ let $ a_n = \vert a_{n-1} - a_{n-2} \vert.$ Does $\sum_n a_n\ $ converge?
Let $a_1$ be linearly independent to $a_2$ over the rational numbers. For $n\geq 3,\ $ let $ a_n = \vert a_{n-1} - a_{n-2} \vert.$ Does $\sum_n a_n\ $ converge?
For example, let $a_1 = 1,\ a_2 = \ln 2=...
- 15.9k
1
vote
1
answer
40
views
Finding $a,b$ such that $ax+by=1$ in a non Euclidean Domain
In Euclidean Domains the Euclidean division algorithm can be used to find $a,b$ such that $ax+by=1$. Let $R$ be a commutative integral domain that is not a Euclidean domain. Assume that $x,y\in R$ ...
- 1,848
0
votes
0
answers
55
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 ...
- 892
2
votes
1
answer
88
views
Showing that $\frac{21n+4}{14n+3}$ is irreducible for every natural number n. [duplicate]
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. ...
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 ...
- 63
0
votes
0
answers
54
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) \\~\\
(...
- 377
0
votes
1
answer
110
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 ...
- 33
1
vote
1
answer
105
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)...
- 13
1
vote
1
answer
40
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 * ...
- 11
0
votes
1
answer
81
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 :
...
0
votes
1
answer
27
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 $...
- 238