# 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.

785 questions
Filter by
Sorted by
Tagged with
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 ...
• 429
57 views

• 358
39 views

• 269
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$ ...
• 269
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 ...
• 1,116
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 ...
• 1,110
1 vote
302 views

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 ...
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 ...
138 views

• 11
84 views

1 vote
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 ...
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\\ ...
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&...
• 11.6k
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 ...
• 181
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$
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}...