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
0answers
25 views

Methods of Computing the Inverse of Y Mod X [duplicate]

I was wondering what methods exist for computing the inverse of Y mod X? Of these, which is the most efficient (time-wise)? I am aware of the Extended Euclidean Algorithm already, just curious what ...
0
votes
1answer
103 views

Proving $\gcd(ga, gb) = g\gcd(a, b)$ intuitively [duplicate]

I am trying to derive by myself $$ \gcd(ga, gb) = g\gcd(a,b), $$ but I am stuck proving it fully. Note, that I avoided reading the relevant proof as I am trying to improve my intuition on the process ...
0
votes
0answers
44 views

Breaking down eucliclean algorithm as a series of movements of the numbers across the number line

I was going over a process that tries to show the euclidean algorithm distilling it to a series of movements across the number line. The basic movements are measured by the $2$ numbers that we are ...
0
votes
0answers
32 views

Reckoning or anthyphairesis: process and intuition

I encountered the process called "Anthyphairesis" which apparently was the basis of the Euclidean algorithm and was also described in Chinese writings under the name "reckoning". A ...
0
votes
0answers
7 views

Calculating the Euclidean distance of joint probabilities

I am reading a paper and in this paper they generate a fake tabular dataset similar to the a real tabular dataset. The dataset could be considered to have records of people like their age, their ...
1
vote
0answers
29 views

Extended Euclidean Coefficients

Given two positive coprime integers $a$ and $b$, we can apply the extended Euclidean algorithm to compute the smallest positive integers $x$ and $y$ satisfying that $ax-by=1$. We can see that $0<x&...
0
votes
0answers
38 views

The number of steps Euclid's Algorithm requires to compute the GCD of $m$ and $n$ is $\Theta(\log n)$ (“SICP 2nd Edition”)

I am reading "Structure and Interpretation of Computer Programs 2nd Edition" by Harold Abelson and Gerald Jay Sussman with Julie Sussman. In this book, there are the following propositions: ...
1
vote
1answer
53 views

Polynomial division of polynomials in two variables

I have the following problem: Let's say I have two polynomials $f,g\in R[X,Y]$ for some domain $R$, and I want to check if $g$ divides $f$. If both $f,g$ were in $R[X]$ then I would do polynomial ...
0
votes
0answers
30 views

Of those domains that were proven to be Euclidean but are not norm-Euclidean, can we really perform Euclidean algorithm in them?

There are domains that are not norm-Euclidean but were proven to be Euclidean using Motzkin's transfinite Euclidean function. In this answer (let's call this answer 1), https://math.stackexchange.com/...
1
vote
1answer
33 views

Finding the inverse of $(x^2+2)$ in the field $S = \Bbb F_3[x]/(x^4+x^3+x^2+1)$

Let $S = \Bbb F_3[x]/(x^4+x^3+x^2+1)$. Find the inverse of $(x^2+2)$ in $S$. I know I'm looking for a polynomial $q(x)$ such that $(x^2+2)q(x) = 1 \mod x^4+x^3+x^2+1$ i.e $(x^2+2)q(x) + k(x)(x^4+x^3+x^...
2
votes
1answer
38 views

Mistake when calculating modular inverse using Euclid's algorithm

So I've attempted calculating the modular inverse of $3$ modulo $68238256$, but my answer is wrong. I know the answer should be $45492171$, but I keep getting $22746085$. I can see that $68238256 - ...
0
votes
0answers
27 views

How do I solve this problem using extended Euclidean Algorithm? 19d $\equiv$ 1 (mod 96) [duplicate]

I understand through trial and error that d=91, but trial and error is extremely inefficient and slow. I understand that you can use the extended Euclidean Algorithm to find d faster, but I'm ...
0
votes
4answers
75 views

Debug back-substitution in extended Euclidean algorithm

I'm trying to find the modular inverse of 28 mod 45 with the Euclidean algorithm but I'm getting the wrong answer. According to online calculators, the answer is $...
0
votes
3answers
52 views

Finding all numbers smaller than $2040$ so that $51 | 71n-24$ [duplicate]

This is a Number Theory problem about the extended Euclidean Algorithm I found: Use the extended Euclidean Algorithm to find all numbers smaller than $2040$ so that $51 | 71n-24$. As the eEA always ...
-1
votes
1answer
223 views

Let $a$ and $b$ be positive integers. If $b=ak$ for some $k \gt 0$ then $2^b − 1 = (2^a)^k − 1 = (2^a − 1)m$ for some $m$. [duplicate]

I came across a homework question asking if this is true or false. After plugging in some numbers, this turned out to be true. May I know a proof or explanation for this? I sort of know this is ...
1
vote
1answer
89 views

Bezout's identity proof

In class, we've studied Bezout's identity but I think I didn't write the proof correctly. I'd like to know if what I've tried doing is okay. These are my notes: Bezout's identity: If $a, \in \mathbb{...
-1
votes
1answer
49 views

Euclid's algorithm tutorial

I am learning about the Euclidean algorithm, and here is an image with the workings. I got stuck towards the end. My friend tried to help me, saying just put the three together. I understand that on ...
2
votes
6answers
113 views

Efficient way to find pairs of multiplicative inverses

Consider the space $\mathbb{Z}_n$, where $n$ is a reasonably large prime, say, for example, 53. How can I quickly and efficiently write out the multiplicative inverses for each element of $\mathbb{Z}_{...
-1
votes
4answers
42 views

Find the GCD of a polynomial using the extended Euclidean algorithm and express it in the form $a(x)f(x)+b(x)g(x)$ [duplicate]

I am working on a problem that I can not seem to finish. Find the gcd of $f(x)=x^7+1$ and $g(x)=x^6+x^5+x^3+1$, and express it in the form $a(x)f(x)+b(x)g(x)$ using the extended euclidean algorithm. I ...
-1
votes
2answers
28 views

Euclidean algorithm and Multiplicative inverse in RSA Cryptosystem

I understand RSA Cryptosystem, the Euclidean algorithm, and mod, however, I can't seem to understand how to solve the following problem. -Use Euclidean algorithm to compute the multiplicative inverse $...
1
vote
0answers
42 views

Public and Private Key in RSA Algorithm Cryptography Number Theory

Anyone know about RSA Algorithm? If you don't, I will explain it. So to get a public and private key in RSA we need two primes number, let $p$ and $q$ be two prime number then we count $n=p.q$ and $\...
2
votes
2answers
64 views

Given that 𝑎 and 𝑏 are positive integers with $𝑎\mid𝑏$, how would one prove that $\gcd(𝑎, 𝑏) = 𝑎$? [duplicate]

I'm having trouble showing that if 𝑎 and 𝑏 are positive integers with 𝑎|𝑏, then 𝑔𝑐𝑑(𝑎, 𝑏) = a. I'm aware that the greatest common divisor of two numbers is the largest number that is a ...
2
votes
2answers
86 views

A Euclidean algorithm problem

Suppose that, after running the Euclidean algorithm on two integers $a$ and $b$, we find that $r_n=3$, where $r_n$ is the last remainder in the Euclidean algorithm. Furthermore, we find that $r_{n-1}=...
0
votes
0answers
31 views

How to find the $R [X]$-linear combination by using the Euclidean algorithm

I just learned the Euclidean division, I know the definition, but when doing the exercise, I have no idea what should I begin with. Here is a question: Let $f :=X^5+3X^4−2X^3−10X^2−2X+4 ∈ Q[X]$ and $g:...
0
votes
0answers
31 views

I don't understand how a certain step has been reached.

I have found the $\gcd(408,126) = 6$. Now I am using Bézout's identity to find the coefficients. a) $408 = 3 * 126 + 30$ b) $126 = 4 * 30 + 6$ Now $6 = 126 – (4 ·30)$ (1) $ = 126 – 4 ·(408 – 3 ·...
1
vote
1answer
20 views

Finding general solution using Euclid's extended algorithm

I have a problem where I'm supposed to find the general equation to $242x+1870y=66$. I used Euclid's extended algorithm to find $x=8$ and $y=-1$, but am not sure how to find all possible solutions ...
2
votes
1answer
59 views

Divisibility of the difference between two very large numbers

I am learning from chapter 1 of the algorithm textbook known as DPV. There is a question 1.11 that asks: Is $4^{1536} - 9^{4824}$ divisible by 35? The whole chapter is on modular arithmetic, modular ...
0
votes
1answer
26 views

Euclid's Division Lemma Extended to Negative Integers Conflict

My textbook states that Euclid's Division Lemma can be extended to all integers with the following information: Let a and b be any two integers with b ≠ 0. Then, there exist unique integers q and r ...
1
vote
1answer
57 views

Euclidean GCD and why does it work? [duplicate]

By the dupe, the table implies $\,(14441,3565) = (3565,189) = \ldots = (28,21) = (21,7) = (7,0) = 7\ \ $ I understand that Euclid's algorithm on GCD is based on doing division via subtraction $x = qy +...
0
votes
0answers
23 views

Division Algorithm: Is slow division equation on Wiki correct?

The slow division algorithm on Wiki appears incorrect given my testing. Does anyone know if this recurrence is correct or works for their sample?: $R_{j+1} = BR_j - q_{n-(j+1)}D$ where $R_j$ is the $...
1
vote
2answers
32 views

Deriving integer solutions to quadratic equation without solving quadratic congruence

I want to generate positive integer solutions of $x$ to the equation: $x^2-x-aT=0$ where a is an integer $>$ 0 and T is a very large positive number. I noticed that when plugging this into wolfram ...
0
votes
0answers
28 views

How do you solve the equation $ax\equiv b \pmod m$ with the extended Euclidean algorithm? [duplicate]

How do you solve the equation $ax\equiv b \pmod m$ with the extended Euclidean algorithm? I saw that you could solve the Diophantine equation $ax-my=b$ I've seen examples but I'm still a bit confused. ...
0
votes
0answers
22 views

Polynomial Long Division Algorithm: question on wiki examples [duplicate]

I was told the algorithm on Wiki for polynomial long division works for $\mathbb{Q}, \mathbb{R}, \mathbb{Z}$. Using this algorithm on Wiki I now understand it over $\mathbb{Q}, \mathbb{R}$, however ...
0
votes
1answer
46 views

How to find the integers $a$ and $b$? [duplicate]

The question says: Find a and b integers where: $671a-654b = 18$ and $\gcd(a,b) = 18$ My attempt was: $a = cd$ where $d$ is $\gcd$ and $c$ is just an integer. $b = kd$ where $k$ is just an integer ...
0
votes
0answers
38 views

Is the summation of Euclidean distance a smooth function?

Assuming I have 10 points (M1 , M2 .... Mn=10) that form a curve in three-dimensional space. Thus, Mi (XMi , YMi , ZMi). To determine the distance from M1 to Mn, I have used the summation of the ...
0
votes
1answer
33 views

Help to understand a simple statement in elementary proof of the euclidean theorem. [closed]

Well, I found an elementary proof for the Euclidean theorem from here : It was okay until I got stuck in $x*b=qx_0b+rb$ : "Indeed, let $x\in E$. We have $x=qx_0+r$ for a unique pair $(q,r)\...
1
vote
1answer
35 views

How are $x \equiv -\frac {JZ}{LX}\pmod {p^D},y \equiv -\frac {J^2YZ}{LX^2}\pmod {p^D}$ calculated?

In this question For what values of $l$ and $j$ (simultaneously) is the following congruence solvable? I do not understand how are $$x \equiv -\frac {JZ}{LX}\pmod {p^D},y \equiv -\frac {J^2YZ}{LX^2}\...
0
votes
1answer
26 views

Base Conversion: Question on common algorithm using Euclidean division

I can see that this algorithm converts bases, however have questions on whats actually going on. The algorithm is presented, then questions follow. Algorithm To convert a number $X$ to base $B$. $k =...
1
vote
0answers
36 views

Euclidean Algorithm in $\mathbb Q[x]$

I've been tasked with finding an element $d\in \mathbb Q[x]$ such that $$(d)=(x^4-x^2+4x, x^3-x+3).$$ To do this, I'm confused at what exactly I'm meant to do to find this element. First I did the ...
0
votes
0answers
24 views

How to compute inverse polynomials modulo an integer [duplicate]

I am working with polynomials in the ring $\mathbb{Z}[X]/(X^n-1)$, so only polynomials with degree at most $n-1$ are allowed, and multiplications must be reduced modulo $X^n-1$. The thing is that I ...
1
vote
0answers
63 views

Proving Eisenstein integers form a Euclidean domain

Let $\omega=\frac{-1+i\sqrt3}{2}=e^{\frac{2\pi i}{3}}$ and define the ring $R = \mathbb{Z}[\omega] = \{a+b\omega\mid a,b\in\mathbb{Z}\}$ with Euclidean function $\phi(a+b\omega)=a^2-ab+b^2$ and show ...
2
votes
0answers
86 views

Is $\mathbb{Z}[i,\varphi]$ a Euclidean domain?

Here $\varphi=\frac{1+\sqrt{5}}{2}$. It's true that $\mathbb{Z}[\varphi]=\mathcal{O}_{\mathbb{Q}(\sqrt{5})}$ is Euclidean since $\mathbb{Q}(\sqrt{5})$ is norm Euclidean, and I've read that $A=\mathbb{...
1
vote
3answers
85 views

Solving a Complex Diophantine Equation with One Known

I am struggling to find a way to implement Euclid's Algorithm in order to solve this diophantine equation. The $N$ will be known and the set of solutions I wish to find will be a set of decreasing $X$ ...
0
votes
1answer
45 views

Euclidean algoritm to get two polynomials

Determine two polynomials in $\mathbb{Z}_5$ so that $$p(x)(x^3+2x^2+3x)+q(x)(x^2+3x+2)=1$$ I know the answer, but not where it comes from. $$p(x)=3x\\ q(x)=2x^2+3x+3$$ With Euclidean algoritm I've got ...
1
vote
2answers
50 views

Given three equivalent statements, prove equality between two sets of variables

What technique should I use to solve the following problem? Would I utilize the division algorithm? Let $ m, n, r, s ∈ \mathbf{Z}$. If $m^2 + n^2 = r^2 + s^2 = mr + ns$, prove that $m = r$ and $n = s$....
1
vote
0answers
65 views

Can an $(a,b)$- knight reach a given point on an infinite chessboard? What moves are needed?

An $(a,b)$-knight is defined here: Can an $(a,b)$-knight reach every point on a chessboard?. Starting from a position $(x_0, y_0)$, it can basically move to $(x_0 + a, y_0 + b)$, $(x_0 + a, y_0 - b)$, ...
0
votes
0answers
81 views

gcd of $ t^n -1 , t^m -1 $, doubt about proof

My teacher was proving the identity $$\gcd(t^m -1 , t^n -1 ) = t^{\gcd(m,n)}-1 $$ he first assumes by induction this rule is true and uses the 'n-m' case, I think to prove it. $$\gcd(t^m -1 , t^{n-m} ...
1
vote
1answer
68 views

How to find a pair of solutions of Linear Diophantine equation such that you minimize this expression?

This is a typical Math coding Problem I encountered here Problem. So Let me break it to you Suppose you have two values $a$ and $b$ and to select this value $a$ one time it takes you $c_1$ cost and ...
0
votes
0answers
48 views

I don't fully understand this algorithm to solve ax + by = gcd(a,b) [duplicate]

An exercise in my number theory book asks to implement the following algorithm to solve $ax + by = gcd(a,b)$: Set $x = 1$, $g = a$, $v = 0$, and $w = b$ If $w = 0$, set $y = \frac{g-ax}{b}$ and ...
2
votes
2answers
92 views

Application of extended Euclidean algorithm

I tried applying the algorithm from Wikipedia in order to calculate $-133^{-1}\mod 256$ I spent already time myself finding the mistake but no success. This is how I did go about applying the ...

1
2 3 4 5
14