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
1answer
56 views

For this broad definition of Euclidean domain, is there a non-trivial example with finite set of norms?

This is a follow-up to the accepted answer to the question Euclidean mapping question. We call an integral domain $R$ Euclidean if there exists a function (called a "norm") $N: R\setminus\{0\...
-1
votes
0answers
132 views

Fast Extended Euclidean Algorithm in Harley's elliptic curves point counting method

Could you help me with Harley's norm computation algorithm that is based on the Fast Extended Euclidean Algorithm that was suggested by Harley in an email to NMBRTHRY list in 2002 and that described ...
2
votes
1answer
33 views

How to find positive coefficients in Bezout's Identity?

I'm trying to find the multiplicative inverse of $10$ modulo $27$ using the extended euclidean algorithm and Bezout's Identity. Using euclids algorithm I find that gcd$(27,10)=1$, and the extended ...
0
votes
1answer
38 views

Optimality of Johnson-Lindenstrauss lemma

Give an example of a set $\mathcal{X}$ of $N$ points for which no scaled projection onto a subspace of dimension $m \ll \log{N}$ is an approximate isometry. Context and hint: this is exercise 5.3.4 ...
0
votes
0answers
31 views

Integer square roots with other terms

Euclidean division permits a nice algorithm for the integer square root which keeps all intermediate values integers, allowing a precise result without leaving $\mathbb{Z}$ (no floating-point). I ...
2
votes
2answers
69 views

A question regarding the proof of $\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$

I have a problem trying to understand the proof: Theorem $\boldsymbol{1.1.5.}$ For natural numbers $a,m,n$, $\gcd\left(a^m-1,a^n-1\right)=a^{\gcd(m,n)}-1$ Outline. Note that by the Euclidean ...
1
vote
3answers
70 views

Visualization for Euclidean Algorithm [duplicate]

I want to really understand the Euclidean Algorithm. A key component in the algorithm is fact that common divisors of two integers are common divisors of their difference. I can see from the ...
0
votes
2answers
32 views

Let $a,b \in \mathbb{Z}$ and let $d = gcd(a,b)$. Show that $\{ ka + lb: k,l \in \mathbb{Z}\} = \{md : m \in \mathbb{Z} \}$

I know that given $d = gcd(a,b)$ that this also means $xa + yb = d$. Using this we get (showing from left to right side) $$xa + yb = d$$ $$m(xa + yb) = md$$ $$xma + ymb = md$$ Now I am unsure how to ...
0
votes
2answers
42 views

Given that $a,b \in \mathbb{Z}$ and are nonzero. Why is it that $\frac{a}{\gcd(a,b)}$ and $\frac{b}{\gcd(a,b)}$ are coprime? [duplicate]

I understand the definition of coprime, which is $\gcd(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}) = 1$ or $x(\frac{a}{\gcd(a,b)}) + y(\frac{b}{\gcd(a,b)}) = 1$. I am pretty sure that I have to use the ...
0
votes
1answer
43 views

when $a$ and $b$ are relatively primes, how is $ax - by= 1$ always possible?

If $a$ and $b$ are relatively primes, with any number of $x$ and $y$, you could always find a set of $x$ and $y$ which makes $ax-by=1$ How is it possible?
0
votes
1answer
37 views

Euclidean algorithm worst case: why never be more than five times the number of its digits (base 10)?

i read the Euclidean algorithm of Wikipedia page(https://en.wikipedia.org/wiki/Euclidean_algorithm). but i was stuck at Worst-case proof. At the second paragraph it says: For if the algorithm requires ...
-6
votes
3answers
38 views

Solve the Diophantine equation [closed]

They ask me to solve: $98x+34y=2$ Please I need help.
2
votes
1answer
33 views

Computational complexity of a modified Euclidean algorithm

The Euclidean algorithm computes the $\gcd$ of two integers with the recursive formula $$\gcd(a,b)=\gcd(b,a\bmod b)$$ and takes at worst $\log_\varphi(\min(a,b))$ steps, where $\varphi$ is the golden ...
2
votes
1answer
51 views

How can I find the max number of times the Euclidean Algorithm must be executed for a given starting remainder?

If each step of the Euclidean Algorithm reduces the remainder by at least 50%, how can I calculate the max number of steps it will take to find the greatest common denominator? If the initial ...
1
vote
1answer
18 views

Find idempotent given generator poly and check poynomial by Bezout algorithm

I have the cyclic code $C$ of length $8$ and dimension $4$ over $\mathbb{F}_3$ and with check polynomial $$g(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^6) = x^4+x^3+x+2$$ where $\alpha \in \...
3
votes
2answers
25 views

Bézout's coefficients, modular inverse

I have to find $14^{-1} (\mod 17)$ I made the equation, $$14x+17y=1$$ By Euclidean division algorithm- $$ 17=14\times1+3 \\ 14=3\times4 +2\\3=2\times1+1$$ If I reverse the process then, $$1=3-2\times1 ...
0
votes
1answer
39 views

Which kind of distance is this one? I want to compare if two images (matrices) are the same

I'm trying to implement a loss function for my neuronal network and I don't know if it is a distance already implemented. I want to compare two black and white images to know how different the two ...
0
votes
1answer
25 views

Algebra(Euclid method)

I couldn’t solve this question and I don’t know how to figure this out from beginning. Hint from my school was to think about euclid method on $ α^m-1,α^n-1$,and better to think $α$ as Polynomial. ...
1
vote
1answer
32 views

Find the remainder of the polynomial $f(x)$ divided by $(x-b)(x-a)$ given its remainder when divided by $x-a$ and $x-b$

I am hoping to get a feedback on my solution to the following problem and if there are better solutions I would love to take a look. Thank you for your time. Let $f(x)$ be a polynomial with ...
3
votes
0answers
39 views

Prove that the smallest positive integers for which the Euclidean algorithm takes $n$ steps are $F(n+1)$ and $F(n)$

Problem The Euclidean state machine is defined by the rule $$(x,y) \rightarrow (y,\mathrm{rem}(x,y)),$$ for $y > 0$. Prove that the smallest positive integers $a\geq b$ for which, ...
0
votes
0answers
53 views

|Discrete Mathematics |The pigeonhole principle + Euclid algorithm?

We've been given in class of Discrete mathematics a problem which we have to prove using the Pigeonhole principle. I've been at it for quite a while. Problem is, English is not my first language and ...
0
votes
1answer
20 views

Elements of quotient ring $\mathbb{Z}_3[x]/I$ being represented as $ax^2 + bx + c + I$ by Euclidean Algorithm?

I came upon this problem in http://sites.millersville.edu/bikenaga/abstract-algebra-1/quotient-rings-of-polynomial-rings/quotient-rings-of-polynomial-rings.pdf, but I don't understand how he applied ...
0
votes
0answers
85 views

Is this a valid proof of the euclidean algorithm?

I created a proof of the euclidean algorithm and since I'm not really familiar with the field of discrete mathematics I'm asking for a revision : Having two natural numbers $a$ and $b$ we follow this ...
0
votes
1answer
30 views

How to apply Chinese Remainder Theorem to polynomials

QUESTION: Find a polynomial $p(x)$ that simultaneously has both the following properties. $(i)$ When $p(x)$ is divided by $x^{100}$ the remainder is the constant polynomial $1.$ $(ii)$ When $p(x)$ is ...
1
vote
1answer
56 views

Find inverse of $[x+1]$ in factor ring $\mathbb{Q}[x]/\left\langle x^3-2 \right\rangle$

Find inverse of $[x+1]$ in factor ring $\mathbb{Q}[x]/\left\langle x^3-2 \right\rangle$. I remember that I need to use the extended Euclidean algorithm, but it has been some time, so I am a bit rusty. ...
0
votes
1answer
42 views

Proof of the Euclidean Algorithm [closed]

How is the euclidean algorithm infallible? An intuitive approach or sketch of the proof would be much appreciated
4
votes
2answers
231 views

Prove that $\gcd\left(n^{a}+1, n^{b}+1\right)$ divides $n^{\gcd(a, b)}+1$

Let $a$ and $b$ be positive integers. Prove that $\operatorname{gcd}\left(n^{a}+1, n^{b}+1\right)$ divides $n^{\operatorname{gcd}(a, b)}+1$. My work - I proved this for $n=2$ but I am not able to ...
-1
votes
4answers
112 views

Last 3 digits of $2^{2017}$

Find the last three digits of $2^{2017}$ My approach: As $125 \times 8=1000$ we have the congruence modulo $$x \equiv 2^{2017}(mod \: 1000)$$ is equivalent to the equations $$x \equiv 2^{2017}(mod \:...
1
vote
0answers
37 views

Why must a Euclidean function map to $\mathbb{Z}^{\ge 0}$?

I'm not sure I get the motivation for a Euclidean function having to map to $\mathbb{Z}^{\ge 0}$. E.g. it would seem that $\mathbb{R}^{\ge 0}$ would be a natural choice for a ring of "polynomials" ...
0
votes
0answers
43 views

Find an upper bound for the number of iterations over the Euclidean algorithm

Let $1\leq y\leq x\leq 2020$ be natural numbers. Find an upper bound for the number of iterations over the Euclidean algorithm on $(x,y)$. I don't have any idea how to solve it. Is it possible to ...
0
votes
1answer
48 views

Use the Euclidean algorithm to find the GCD of $1 + 28i$ and $4 + 7i$

I am trying to learn how to use the Euclidean algorithm to find the GCD of $1 + 28i$ and $4 + 7i$. The question I am trying to answer is: Apply the Euclidean algorithm to $\alpha = 1 + 28i$ and $\...
0
votes
0answers
28 views

Applying Euclidean Algorithm to find nth value

Stuck on two questions which I am unsure of how to approach. Use Euclidean Algorithm to find the $n$ value: $\text{gcd}(a,b)$ expressed as $\text{gcd}(a,b) = \text{gcd}(a_{1},b_{1}) = \text{gcd}(a_{...
1
vote
1answer
29 views

Prove that : $\text{gcd}\bigg(a+b, \frac{a^p+b^p}{a+b}\bigg)=1 \ \text{or} \ p$

If $p$ is an odd prime and $a,b$ are relatively prime integers, prove that : $$\text{gcd}\bigg(a+b, \frac{a^p+b^p}{a+b}\bigg)=1 \ \text{or} \ p$$ Since it's obligatory to show the attempts to avoid ...
1
vote
5answers
74 views

If $f(x)$ is a common factor of $g(x)$ and $h(x)$ find $f(x)$

Given that $f(x)$ is a common factor of $g(x)=x^4-3x^3+2x^2-3x+1$ and $h(x)=3x^4-9x^3+2x^2+3x-1$ find $f(x)$ I tried to factorised $g(x)$ but it doesn't have any rational roots as I've already tried ...
0
votes
0answers
28 views

GCD / proof by induction / well founded order

$f(x,y) := \begin{cases} f(x-y,y) \hspace{0.5cm} if \hspace{0.5cm} x > y\\ f(x, y-x) \hspace{0.5cm} if \hspace{0.5cm} y > x\\ x \hspace{2.2cm} ...
0
votes
1answer
19 views

Euclids algorithm for all integer polynomials

I am going through a proof of a question that asks: Prove $\langle$x+1,x$^2$+1$\rangle$ is a maximal ideal in $\Bbb Z$[X] The proof shows that this ideal is equal to $\langle$x+1,2$\rangle$ and then ...
2
votes
1answer
92 views

Find the maximum value $LCM$ pair in the sequence where $LCM(a, b)$ means the smallest positive integer that is divisible by both.

Problem Statement: Given a sequence $S$ of $N$ positive numbers, calculate the $\max\limits_{1 \le i < j \le n} LCM(a_i,a_j)$, where $LCM(a, b)$ is the smallest positive integer that is divisible ...
0
votes
0answers
19 views

epsilon neighbourhood for polar data

I am having a density-based radar database that I try to cluster with a grid-based DBSCAN algorithm. The part of the algorithm my question focuses on is "the core point condition". Which is basically ...
0
votes
2answers
21 views

Finding GCD of powers and factorial numbers

I need some help with trying to find the GCD of $23!$ and $2^{31}$. I tried writing out the prime factor of 23! but I am still left with lots of exponents. However, the prime factorial of $23!$ ...
1
vote
0answers
39 views

$\Bbb Z / 3 \Bbb Z[x]/I$ and $(\Bbb Z / 3 \Bbb Z[x]/I)/J$ quotients rings. Prime elements.

I need some help with this exersise because it mixes quotients rings, concruences, ideals, polynomials and it mess me up. I don't even know how to start. Any help will be appreciated. Let $R=\Bbb Z / ...
2
votes
2answers
46 views

Proving a quadratic equation has no integral roots

Question: Show that the quadratic equation $x^2-7x-14(q^2+1)=0$ where $q$ is an integer ,has no integral real roots. My approach : Let for any integer $x$ the quadratic equation $=0$, Then $x(x-...
-2
votes
2answers
61 views

Calculating remainder when a polynomial I'd divided by another polynomial

Let $p(x)$ be a polynomial such that when $p(x)$ is divided by $x - 19$ the remainder is $99$, and when $p(x)$ is divided by $x - 99$ remainder is $19$. Find the remainder when $p(x)$ is divided by ...
0
votes
0answers
30 views

How does the Euclidean algorithm apply to horse racing?

Given that the virtual grand national took place yesterday, I was reading up about how mathematics and statistics was used to give the results of the race. I was just curious as to how exactly this is ...
1
vote
1answer
19 views

Hopefully a better solution than mod-bashing with Euler

Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime positive integers $a>1$ and $b>1$ such that $a^b+b^a$ is divisible by $a+b$. So I have a solution involving mod-...
1
vote
2answers
53 views

Euclid's algorithm to find multiplicative inverses over a polynomial field [duplicate]

I'm trying to find the multiplicative inverse of $\overline{x+1}$ over the field $\mathbb{F}_3[x]/(x^3 + 2x + 1)$. I know I need to use Euclid's algorithm to do so, but I keep running into some ...
1
vote
1answer
40 views

Prove that $n \text{ mod } r < \frac{n}{2}$ [closed]

I am trying to prove a section of the Euclidean Algorithm for greatest common factors which states: $\gcd(m, n) = \gcd(n, r) = \gcd(r, n \text{ mod } r)$, where $r =m \text{ mod } n$ Prove ...
4
votes
2answers
354 views

Extended Euclidean Algorithm: why does it work?

I find myself able to mechanically apply the "extended" Euclidean algorithm to find the gcd of two integers and to write a linear combination by working backwards. However, I do not have a good grasp ...
0
votes
0answers
7 views

matching pursuit algorithm for data reconstruction in routing protocol

I am trying to understand the compressed sensing theory Energy and Delay Aware Data Aggregation in Routing Protocol for Internet of Things in Algorithm 3: Data Reconstruction Using Matching ...
0
votes
1answer
55 views

Can GCD (Euclidean algorithm) be defined/extended for finite fields (interested in $\mathbb{Z}_p$) and if so how

I am interested in defining / extending gcd (and possibly euclidean algorithm) over the finite field $\mathbb{Z}_p$ (that is over integers modulo a prime $p$). The ...
0
votes
3answers
52 views

Multiplicative Inverse Calculation

I have a moduli set: $$\{m_0,m_1,m_2\}=\{2^n - 1, 2^n, 2^n +1\}.$$ If we define $M_2 = m_0*m_1 = 2^{2n} - 2^n$, how can we find the multiplicative inverse of $M_2$ modulo $m_2$? The answer in the ...

1
2 3 4 5
12