# Tag Info

## Hot answers tagged euclidean-algorithm

63

Perhaps the easiest way to do it by hand is in analogy to Gaussian elimination or triangularization, except that, since the coefficient ring is not a field, one has to use the division / Euclidean algorithm to iteratively descrease the coefficients till zero. In order to compute both $\rm\,gcd(a,b)\,$ and its Bezout linear representation $\rm\,j\,a+k\,b,\,$ ...

46

Using the Euclid-Wallis algorithm (described below) $$\begin{array}{r} &&4&2&1&7\\\hline 1&0&1&-2&3&-23\\ 0&1&-4&9&-13&100\\ 100&23&8&7&1&0\\ &&&&{\uparrow}&{\star} \end{array}$$ lookng below the horizotal line, the top row times $100$ plus the middle row ...

28

$100x -23y = -19$ if and only if $23y = 100x+19$, if and only if $100x+19$ is divisible by $23$. Using modular arithmetic, you have \begin{align*} 100x + 19\equiv 0\pmod{23}&\Longleftrightarrow 100x\equiv -19\pmod{23}\\ &\Longleftrightarrow 8x \equiv 4\pmod{23}\\ &\Longleftrightarrow 2x\equiv 1\pmod{23}\\ &\Longleftrightarrow x\equiv 12\... 22 You don't need the Euclidean algorithm for this scenario. If a,b are positive integers, and a|b, then \gcd(a,b) = a. Hence, if a,n are positive integers, then \gcd(a,a^n)=a. But if you choose to use the Euclidean algorithm, just for the sake of it, then when you reach zero remainder, the \gcd is the divisor that produced the zero remainder, ... 18 You're probably overthinking it. Let q = x \cdot y^{-1}, which always exists, because F is a field, and y \ne 0. So let r be zero, and you don't need to worry at all about the valuation. 17 Any number that is coprime to a modulus will have an inverse, so we need to find 5 consecutive numbers that share a factor with 70. 70 has three primes factors: 2,5,7. Of any 5 consecutive numbers, two or three will be even, but at most one will be divisible by 5 or 7. So we need three even numbers with an odd multiple of 5 and an odd ... 13 The number of steps required to compute \gcd(a,b) is given by the length^{(*)} of the continued fraction of \frac{a}{b}. It follows that the worst-case scenario for the Euclidean algorithm is given by the convergents of \varphi=\frac{1+\sqrt{5}}{2}=[1;1,1,1,1,\ldots], i.e. by consecutive Fibonacci numbers. (*) Explanation: assuming a>b, a step ... 11 HINT \displaystyle\rm\ \ mod\ 23:\ x\: \equiv\: \frac{-19}{100}\: \equiv\: \frac{4}{100}\: \equiv\: \frac{1}{25}\: \equiv\: \frac{24}{2}\: \equiv\: 12\:,\  i.e. \rm\ x\: =\: 12 + 23\ n\:. 11 This is more a comment on the method explained by Bill Dubuque then a proper answer in itself, but I think there is a remark so obvious that I don’t understand that it is hardly ever made in texts discussing the extended Euclidean algorithm. This is the observation that you can save yourself half of the work by computing only one of the Bezout coefficients. ... 11 The field \Bbb F_9 of order 9 is (as a ring) not isomorphic to the ring \Bbb Z / 9 \Bbb Z of integers modulo 9. (In fact, even the underlying additive groups of the two rings are nonisomorphic: \Bbb Z / 9 \Bbb Z has elements of order 9 under addition, but all nonzero elements of \Bbb F_9 have order 3 under addition.) To construct \Bbb F_9, ... 11 Use the expansion (1+x^3)=\left( x+1 \right) \left( {x}^{2}-x+1 \right). Then \frac{1}{1+\sqrt{2}}=\frac{1-\sqrt{2}+(\sqrt{2})^2}{(1+\sqrt{2})(1-\sqrt{2}+(\sqrt{2})^2)}=\frac{1-\sqrt{2}+(\sqrt{2})^2}{3}=\frac{1}{3}-\frac{\sqrt{2}}{3}+\frac{(\sqrt{2})^2}{3} $$11 Although \mathbb{Z}[\sqrt{14}] is not norm-Euclidean, you haven't proved it yet. At least, you can successfully get through one step of the Euclidean algorithm:$$3 = (7+2\sqrt{14})(-2+\sqrt{14}) + (-11 - 3\sqrt{14}),$$and the absolute value of the norm of -11 - 3\sqrt{14} is 5, which is less than the absolute value of the norm of 7+2\sqrt{14}, ... 10 Well, the Euclidean algorithm may not work in the integral domain {\Bbb Z}[x], since in order to form the division of f by g, the divisor g need to be monic (or more generally, the leading coefficient must be invertible, here \pm 1). Moreover, the gcd of 2 and x is 1, but has no representation$$2a+xb=1$$for some a,b. The reason is that ... 8 Starting from the "snag" given in the OP and unrolling the Euclidean algorithm backwards, one can easily construct a sequence continuing long before hitting a snag. Formally, we construct a sequence (w_n)_{n\geq 1}, such that w_1=2,w_2=1+\sqrt{-5} (the initial "snag"), \frac{w_n}{w_{n+1}} rounds to zero (more precisely, \frac{w_n}{w_{n+1}}=x_n+y_n\... 7 No. Consider the Euclidean domain \mathbb R[x], which has Euclidean norm \nu(f)=\mathrm{deg}(f). Then for example x^2+1 and x^2+x+1 have the same norm but are not associates, as the units are nonzero elements of \mathbb R. 7 If you take the equation mod 23, you find 8x \equiv 4 \pmod{23} and by inspection, this is satisfied by x \equiv 12 \pmod{23}. To find this, you use the Extended Euclidean algorithm 7 \begin{eqnarray}\!\text{By the distributive law}\ \ && \,8\, -\, 1\cdot(999-8\cdot 124)\\ &=&\ 8\cdot\color{#c00}1\, -\, 999\, +\, 8\cdot\color{#c00}{124}\\ &=&\ 8\cdot\color{#0a0}{ 125} - 999\ \ \,{\rm by}\ \ \color{#c00}{124 + 1} = \color{#0a0}{125}\end{eqnarray} This "back-substitution method" for the extended gcd is ... 7 If you know$$15=7(2)+1$$Let's consider \mod 15$$0\equiv7(2)+1 \mod 157(-2) \equiv 1 \mod 15$$Hence$$(13)7\equiv 1 \mod 15$$7 The point is that when you get a zero divisor in the Euclidean Algorithm, dividend is the GCD. In this case, the zero pops up more quickly than in most other cases. 7 Hint: On every iteration, (a,b) is replaced by (b,a\bmod b). The worst case occurs when the decrease a-b is the smallest, and this occurs when the integer quotient is b/a=1 (so that a\bmod b=a-b). By its very definition, the Fibonacci sequence has this property at every step. Now if F_k\le b\le F_{k-1} for some k, the number of iterations ... 7 SOME EXAMPLES OF PRINCIPAL IDEAL DOMAINS WHICH ARE NOT EUCLIDEAN AND SOME OTHER COUNTEREXAMPLES. Abstract. It is well known that every Euclidean ring is a principal ideal ring. It is also known for a very long time that the converse is not valid. Counterexamples exist under the rings R of integral algebraic numbers in quadratic complex fields Q[\... 6 It is the same argument as the one for the Gaussian integers. Let w and z be in our ring. We want to show that there exist numbers q and r in our ring such that w=zq+r, and N(r) \lt N(z), where N is the usual norm. Consider the complex number \frac{w}{z}. There are real numbers s and t such that \frac{w}{z}=r+s\sqrt{2}i. Let a be ... 6 You may like to check this and this. Also, there is a well known table method which is very easy and fast for the manual solution. 6 You can base an algorithm on the following theorem:$$P(m)\subseteq P(n)\iff \begin{cases} m=1\\\quad\text{or}\\ (m,n)\gt1\text{ and }P(m/(m,n))\subseteq P(n) \end{cases}$$where (m,n)=\gcd(m,n). Borrowing one of Steven Gregory's examples, let's show that P(120)=P(450) by showing first that P(120)\subseteq P(450) and then that P(450)\subseteq P(... 6 The euclidean algorithm works just as usual. We have$$ \gcd(21n+4,14n+3)\\ =\gcd(21n+4-(14n+3),14n+3)\\ =\gcd(7n+1,14n+3)\\ =\gcd(7n+1,14n+3-2(7n+1))\\ =\gcd(7n+1,1)=1 $$6 Note that x \in \mathbb{N} has an inverse modulo n if and only if \text{gcd}(x,n) = 1. Looking for the prime decomposition of 70, we see that$$70 = 2 \cdot 5 \cdot 7.$$Now clearly 4, 5, 6, 7, 8 don't have greatest common divisor 1 with 70 and therefore no inverse modulo 70. 6 Using Fermat's little theorem, we have$$4^{28k +m} \equiv 4^{m} \pmod{29}.$$As such,$$4^{2018} \equiv 4^2=16 \pmod{29}.

6

At least in quadratic integer rings with unique factorization, if the Euclidean algorithm doesn't work, you can always just look at the prime factorization. For example, of the infinitely many imaginary quadratic integer rings, only nine have unique factorization, and of those nine, only five are Euclidean. In an answer to What is a concrete example to ...

6

The paper below attacks exactly this problem: Heinrich Rolletschek, On the Number of Divisions of the Euclidean Algorithm Applied to Gaussian Integers, Journal of Symbolic Computation 2 (1986), no. 3, 261–291. He proves an analogue of Lamé's theorem about the maximum number of steps but it seems that finding pairs that attain this maximum remains an open ...

5

In $\mathbb Z[i]$, we have $N(1+7i)=50=N(5+5i)$ but $1+7i$ and $5+5i$ are not associates.

Only top voted, non community-wiki answers of a minimum length are eligible