Skip to main content

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

Euclidean algorithm in commutative rings with unity [duplicate]

Let R be a commutative ring with identity, and J an ideal generated by the members $a^n-1$ and $a^m-1$ for some $a \in R$ and $n, m$ positive integers. I want to establish that the principal ideal ...
giorgio's user avatar
  • 429
0 votes
1 answer
57 views

The state machine for "Extended Euclidean Gcd Algorithm" terminates after at most the same number of transitions as that of the Euclidean algorithm

This is one following question based on one question I asked before In spring18 mcs.pdf, it has Problem 9.13: Define the Pulverizer State machine to have: $$ \begin{align*} \text{states} ::=&...
An5Drama's user avatar
  • 358
0 votes
1 answer
55 views

Why is the Pulverizer machine partially correct?

In spring18 mcs.pdf, it has Problem 9.13: Define the Pulverizer State machine to have: $$ \begin{align*} \text{states} ::=& \mathbb{N}^6&\\ \text{start state} ::=& (a, b, 0, 1, ...
An5Drama's user avatar
  • 358
-1 votes
1 answer
39 views

What have I missed here in this Euclidean algorithm trying to find D of RSA

Given the RSA public key find the decryption key d and decrypt the ciphertext c=8. Known information: n=119, p=17, q=7, e=13 $\phi(n) = (p-1)(q-1) = 16\times 6=96$ Equation for finding d: $$ed\...
Alix Blaine's user avatar
1 vote
1 answer
74 views

RSA finding D key

Given the RSA public key find the decryption key d and decrypt the ciphertext c=5. Known information: n=221, p=17, q=13, e=11 $\phi(n) = (p-1)(q-1) = 16\times 12=192$ Equation for finding d: $$ed\...
Alix Blaine's user avatar
-1 votes
4 answers
44 views

Use the Euclidean algorithm steps to find ALL the integer solutions of the equation [duplicate]

Use the Euclidean algorithm to find ALL the integer solutions of the equation: $$5x+72y=1$$ My attempt: $5x + 72y =1$ $72 = 14 \times 5 + 2 \quad (14~obtained~by~72/5 = 14.4)$ $5 = 2 \times 2 + 1$ ...
Alix Blaine's user avatar
4 votes
1 answer
107 views

Minimal size of $a^2+b^2$ such that $ad-bc=1$

If $c,d$ are two relatively prime positive integers, then we can find integers $a,b$ such that $ad-bc=1$. But $a$ and $b$ are not unique: we can replace $a$ with $a+kc$ and $b$ with $b+kd$ for any ...
Math101's user avatar
  • 1,116
4 votes
0 answers
99 views

Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$

As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
Juan Moreno's user avatar
  • 1,110
1 vote
3 answers
302 views

About reversing the Euclidean Algorithm, Lemma of Bézout

From the book Discrete Mathematics for Computing 2nd Edition in eBook: I know how to perform the Euclidean Algorithm and GCM(a,b). I am however, deeply confused by this: $$1 = 415 - 69(421 - 1 \times ...
Alix Blaine's user avatar
0 votes
0 answers
26 views

Is the sum of the continued fraction sequence / number of steps in Euclid algorithm a metric?

It seems to me that the sum of the continued fraction sequence minus one can serve as a metric on positive rational numbers. Given a positive rational number $q=[a_0, a_1, ...]=a_0+\frac{1}{a_1+\dots}$...
Alexandre's user avatar
  • 271
0 votes
0 answers
40 views

Find integral values of x , y and z : $6x +10y + 15z= -1$ [duplicate]

I have done similar type of questions before by using the Euclidean Division Lemma/Algorithm to rewrite the equation and then find the solution, but those were problems with only two variables. In the ...
1025's user avatar
  • 19
0 votes
0 answers
60 views

A simple algorithm to find the inverse [duplicate]

Someone showed me such an algorithm. I'm going to explain his method with an example. Let's say we're looking for $$37^{-1}\in \mathbb Z/63\mathbb Z$$ First, we make the successive divisions of Euclid'...
Stéphane Jaouen's user avatar
1 vote
1 answer
96 views

What is the probability a random integer $x$ when divided by $3$ has a remainder smaller than when $x$ is divided by $9$? without monte-carlo.

I noticed the quantity of numbers from 1-100 with remainder zero modulo nine = quantity of numbers from 1-100 with remainder one modulo nine > quantity of numbers from 1-100 with remainder 2 modulo ...
user avatar
1 vote
1 answer
102 views

An intuitive, geometric and informal proof of the Euclidean algorithm

The version of the Euclidean algorithm that I'm trying to prove is as follows: $$\text{For natural numbers $a$ and $b$ such that $a \geq 1,$ $b \geq 0$ and $a \geq b,$ gcd($a,b$) =} \begin{cases} a, &...
Kushagr Jaiswal's user avatar
0 votes
0 answers
34 views

If we have the Bezout coefficient, how to find the smallest possible coefficient that can take its place? [duplicate]

The question is the following: "Determine the pair of numbers m,n such that gcd(1234,5678)=1234⋅m+5678⋅n for which n is the smallest positive integer". I found that m=704 and n=-153. But n ...
Nare Avetisyan's user avatar
2 votes
1 answer
90 views

Definition of "division with remainder" for rings?

Turns out that I cannot find such thing as "the definition of division with remainder" for rings. It is all good if we specify integers, polynomials, etc, were one division with remainder is ...
dragomang87's user avatar
0 votes
0 answers
138 views

Seeking Help Understanding Specific Terms in 7-adic and 5-adic Euclidean Algorithms

Using the 7-adic Euclidean Algorithm for $\frac{181625}{11}$ and $\frac{9360}{11}$: $\frac{181625}{11} = (2)\left(\frac{10555}{2}\right) + \left(\frac{9360}{11} \cdot 7^1\right)$ $\frac{10555}{2} = \...
Estudiante Inversa's user avatar
0 votes
0 answers
47 views

Logic behind the Extended Euclidean Algorithm

Thank you beforehand for reading my question. In the terms that I want to understand the Extended version of the Euclidean Algorithm, I understand the Euclidean Algorithm as follows: You find the ...
Anthony's user avatar
0 votes
0 answers
52 views

Extended Euclidian algorithm for polynomials [duplicate]

this question follows one from yesterday that got deleted because it was a duplicate. The problem was about solving this equation (in $ℚ[x]$) : $$f(x)(2x^3 + 3x^2 + 7x + 1) + g(x)(5x^4 + x + 1) = x + ...
AANICR's user avatar
  • 93
0 votes
1 answer
107 views

Algebra: find polynomials $M(x)$ and $N(x)$ such that $x^{m}M(x)+(1-x)^{n}N(x)=1$.

Find polynomials $M(x)$ and $N(x)$ such that $$ x^{m}M(x)+(1-x)^{n}N(x)=1. $$ Here are my thoughts about the problem. If I substitute $0$ in the left side of equation I get $f(0)=N(0)=1$, so I have ...
bob's user avatar
  • 39
1 vote
1 answer
82 views

Calculating the gcd of two polynomials in integers using a prime field

Let $f, g \in \mathbb{Z}[x]$. Let also $h \in \mathbb{Q}[x]$ be the $\gcd(f,g)$ found by the Euclidean algorithm. Now, for $p$ an odd prime, let $h^* \in \mathbb{Z}/p\mathbb{Z}[x]$ be the $\gcd(f,g)$ ...
Max Bow-Arrow's user avatar
0 votes
0 answers
49 views

How to compute inverses in $\mathbb{Q}[x] / \langle x^3 + 3x + 3 \rangle$ [duplicate]

When working in the field $\mathbb{Q}[X] / \langle X^3 + 3X + 3 \rangle$, let $a$ represent the image of $X$ under the natural quotient mapping. I am trying to understand the range of strategies that ...
B.H.'s user avatar
  • 1
0 votes
0 answers
13 views

L2 distance computation with given L2 distance to triangle nodes.

In a triangle with three points A, B, and C. The L2 distance between each pair of points |AB|, |AC|, |BC| is given. For the other two points O and P, the distance to the three points is given, i.e. |...
Yujian S's user avatar
0 votes
0 answers
49 views

help with Lamé's Theorem (Knuth) induction step

I am trying to prove a part of the therom stating: let $a,b\in \Bbb N$ such that $1 \lt b \lt a$ assume euclidean algorithm takes n steps show that $b\ge F_n$ where $F_n$ is the nth fibonacci number. ...
Gidfuck's user avatar
  • 61
1 vote
0 answers
334 views

What is the correct formula for Within Cluster Sum of Squares

I am studying clustering with K-Means algorithm and I got stumbled in the "inertia", or "within cluster sum of squares" part. First I would appreciate if anyone could explain me ...
Artur Juan Dantas's user avatar
0 votes
2 answers
158 views

Prove there is a polynomial $d(x) \in \mathbb Q[x]$ that is a gcd of $f(x)$ and $g(x)$ and whose term of minimal degree is $d_rx^r.$ (D&F #9.3.5(a)).

Here is the question I am trying to understand its solution: Let $R = \mathbb Z + x \mathbb Q[x] \subset \mathbb Q[x]$ be the set of polynomials in $x$ with rational coefficients whose constant is an ...
Intuition's user avatar
  • 3,161
1 vote
0 answers
49 views

Exended Euclidean algorithm, row reduction of Sylvester matrix, and gcd

Let $f,g\in A[x]$ with $A$ a commutative ring. Suppose $f$ is monic (for convenience), so that $A[x]/\langle f\rangle $ is a free $A$-module. If I understand correctly, the extended Euclidean ...
Arrow's user avatar
  • 13.8k
0 votes
2 answers
99 views

Determine an angle in two overlapping triangles

A triangle $ABC$ is given as shown below. We know that $i = i_1$ and $k = k_1 = k_2$. Determine angle $\gamma$ $geometrically$. Note: Through variations in 'geogebra' I think that $\gamma = \frac{3}{4}...
Marie L's user avatar
  • 53
0 votes
0 answers
14 views

How does the reduction work in backwards substitution in Bézout's identity? [duplicate]

I'm a bit stuck on one part of Bézout's identity when used with Euclid's algorithm. The specific part of the equation I can't see is; ...
CoedFoel's user avatar
1 vote
0 answers
83 views

Lang's proof of Euclidean algorithm for power series

I have a question about the use of projections in Lang's proof of the Euclidean division algorithm for power series (Algebra - Serge Lang, Chapter IV, section 9, Theorem 9.1). Specifically, there is a ...
Zahra Abdullah's user avatar
1 vote
0 answers
31 views

If $n, d \in \mathbb{N}$ are such that $d < n$, show that $n = c_0 + c_1d+ \cdots + c_kd^k$ with each $c_i \in \mathbb{Z}$ such that $0 \leq c_i < d$.

I am trying to prove one of the early questions in Serge Lang's Undergraduate Algebra textbook (Question 1 on Section 1.5) and I am not sure if I have proven it correctly. Let $n, d \in \mathbb{N}$ ...
maraik2002's user avatar
4 votes
0 answers
78 views

Alternating sum of the length of intervals

Here's the problem For two odd $m$ and $n$, which are coprime, consider the interval $[0, mn]$ and let $$ A = \{0, m, 2m, \dots , nm\} \quad\text{and}\quad B = \{0, n, 2n, \dots , mn\}. $$ ...
Cheese's user avatar
  • 41
1 vote
1 answer
201 views

Is it possible for integer division in C++ to express a compact mathematical condition, as for Euclidean division?

I am studying integer division in C++. At the same time, I read the wikipedia article 'Euclidean division'. In this article there is such a lemma: ...
Ilya Chalov's user avatar
1 vote
1 answer
51 views

Number of steps in subtractive Euclidean algorithm

Given 2 non-negative integers a, b that range between (1 and 1e9), let c = |a - b| and after calculating c let a = b, b = c then recalculate c. what is the number of operations needed for c to reach 0....
Youssef Tarek's user avatar
0 votes
0 answers
214 views

In a Euclidean domain $R$, every element with minimum norm is a unit.

I'm having trouble with the Claim: In a Euclidean domain $R$, every element with minimum norm is a unit. The proofs I have seen say, e.g., $1 = q a + r$, where $a$ has minimum norm $N(a) = m$. Then, $...
Cliff's user avatar
  • 105
1 vote
1 answer
63 views

Why can $\frac{2x^3-3x^2+2x-4}{x^2+4}$ be expressed as $2x-3 +\frac{-6x+8}{x^2+4}$?

Let's say we have an improper function: $$P(x) = \frac{2x^3-3x^2+2x-4}{x^2+4}$$ If we do long division why does the polynomial can be expressed as "quotient + reminder/divisor" $$P(x) =2x-3 +...
SirMrpirateroberts's user avatar
0 votes
0 answers
37 views

Is $\gcd(a^n-1,a^nm) = \gcd(a^n-1,m)?$ [duplicate]

I came across this procedure while trying to solve $gcd((2^{100})-1,(2^{120})-1))$, the procedure yielded correct result. E.g $gcd((2^{120})-1,2^{100}-1))$ =$gcd((2^{100})-1,2^{120}-2^{100}))$ = $gcd((...
Optimus's user avatar
  • 11
4 votes
0 answers
84 views

The Euclidean Algorithm and Integer Factoring

Theorem 1. Let $N=pq+rs$ where $p=q+r+s$. Then $N=(q+r)(q+s)$. Proof. Let $N = pq + rs$ and $p = q+r+s$. Then, $$ \begin{align} N & = (q+r+s)q + rs \newline & = q(q+r) + s(q+r) \newline &...
vvg's user avatar
  • 3,331
0 votes
1 answer
273 views

How to calculate the modular inverse from the bezout coefficients?

I have the following equation $$P = c \cdot w^{-1} \bmod m.$$The known values are $c = 1503, w = 444$ and $m = 821$. I really don't know, how to get $w^{-1}$ (solution says it's 723). I used the ...
sp8cky's user avatar
  • 3
0 votes
1 answer
77 views

discrete mathematics, Euclidean algorithm [duplicate]

I'm having troubles to find the coefficients: 1357𝑎 + 49𝑏 = 1 = 𝑔𝑐𝑑(1357,49). I started solving the equations by the Euclidean algorithm, but I can't replace them all. Can someone help me? From ...
Mariana Monteiro's user avatar
1 vote
3 answers
85 views

Polynomial gcd of $x^5+x+1$ and $x^2+1$

In a multiple choice assignment I had to find the gcd of $$x^5+x+1$$ and $$x^2+1$$ I can find it with the Euclidean algorithm, but that is taking me quite some time and work. Since this test was ...
no1dea's user avatar
  • 77
0 votes
0 answers
10 views

Finding smaller pseudofactors modulo N

In the paper "Shor's algorithm with fewer (pure) qubits", Zalka points out that a multiplication by an arbitrary constant $C$ modulo $N$ can be reduced in cost by finding smaller values $c_1$...
Craig Gidney's user avatar
  • 2,144
1 vote
1 answer
134 views

Solving the congruence $3x \equiv 17 \pmod{29}$ [duplicate]

The given linear congruence is to be solved: $$\gcd:(3;29)=1 |17$$ $$3x+29y=1 \iff 3x \equiv 1 \pmod{29} \iff y \equiv 3^{-1} \pmod{29}$$ With the extended Euclidean algorithm one obtains: \begin{...
user avatar
2 votes
2 answers
96 views

Finding the minimum of $z+d$?

Suppose that $z, d\in \mathbb{Z}$ are a $3$-digit positive integer with $24\text{gcd}(z, d) = \text{lcm}(z, d)$. How can we find the minimum of $z+d$? $$\begin{align}\text{gcd}(z, d)\text{lcm}(z, d) = ...
user avatar
1 vote
0 answers
70 views

Why Hurwitz 's lemma is called as a weak generalization of the Euclidean Algorithm?

Why Hurwitz's lemma(Hurwitz's lemma says that there exists a positive integer M with the following properties that for a,b(nonzero)belongs to ring of integers there is a t, 1<=t<=M & w ...
Himasish Ghosal's user avatar
0 votes
1 answer
117 views

Magic square $29\times29$: Linear Congruences and Uniform Step Method

This linear congruency I was given is part 1 to a 2 part question, I was able to get this. [ \begin{split} 14\cdot27(x+y)\equiv14\cdot16&\pmod{29}\Longrightarrow\\ ...
spice_math_guy's user avatar
0 votes
0 answers
58 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&...
Karl's user avatar
  • 11.6k
8 votes
1 answer
154 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 ...
impomatic's user avatar
  • 181
0 votes
2 answers
44 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$
chrisware's user avatar
0 votes
1 answer
107 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}...
mLstudent33's user avatar

1
2 3 4 5
16