Intereting Posts

Primes dividing $11, 111, 1111, …$
Can all rings with 1 be represented as a $n \times n$ matrix? where $n>1$.
To show that $S^\perp + T^\perp$ is a subset of $(S \cap T)^\perp$
This integral is defined ? $\displaystyle\int_0^0\frac 1x\:dx$
Differentiable injective function betweem manifolds
Calculator algorithms
Finite Extensions and Bases
Normed vector space with a closed subspace
Pairing function for ordered pairs
What operations can I do to simplify calculations of determinant?
Finding a primitive element of a finite field
Let $\alpha \in \overline{\Bbb Q}$ a root of $X^3+X+1\in\Bbb Q$. Calculate the minimum polynomial of $\alpha^{-1}$ en $\alpha -1$.
Integral of $R(R^2+y^2)^{-3/2}$ with respect to $y$
Spivak's Calculus – Chapter 1 Question 1.3
Sum of elements of inverse matrix

Let m and n be natural numbers. Suppose $ min(m, n) \leq 2^k $ for some natural number k. Show that the Euclidean algorithm needs at most $ 2k $ iterations to find the GCD of m and n. Basically I have no clue how to start this proof, I think I should be looking at the remainders and somehow showing that $ a_{k+2} \leq \frac{a_{k}}{2} $ where $a_{k}$ represents the kth remainder. Other than that, I have no clue about where to begin.

- Extended Euclidean Algorithm, what is our answer?
- finding units of $ \mathbb{Z} {3}] $
- How to use the Extended Euclidean Algorithm manually?
- $15x\equiv 20 \pmod{88}$ Euclid's algorithm
- Information about Problem. Let $a_1,\cdots,a_n\in\mathbb{Z}$ with $\gcd(a_1,\cdots,a_n)=1$. Then there exists a $n\times n$ matrix $A$ …
- The ring $\mathbb Z= \{a+b\sqrt{-2} ; a\in \mathbb Z,b\in \mathbb Z \}$ has a Euclidean algorithm
- Visualizing tuples $(a,b,x,y)$ of the extended Euclidean algorithm in a four-dimensional tesseract. Are there hidden symmetries?
- Bezout's Theorem
- Generalisation of euclidean domains
- Finding $d=\gcd(a,b)$; finding integers $m$ and $n$: $d=ma+nb$

In two steps we move from $(m,n)$ to $(m’=n,n’=m\bmod n)$ and then to $(m”=n’,n”=m’\bmod n’)$.

Assume $n\le 2^k$. Then $m’,n’\le 2^k$ and $n”\le \min\{m’,n’,|m’-n’|\}$. Henc $n”>2^{k-1}$ could only happen if both $|m’-n’|>2^{k-1}$ and $\min\{n’,m’\}>2^{k-1}$, which implies $\max\{m’,n’\}>2^{k-1}+2^{k-1}=2^k$, contradiction.

Hence after two steps $n\le 2^k$ becomes $n”\le 2^{k-1}$

Hence if $n\le 2^k$ initially, then after $2k$ steps we arrive at a situation with $n\le 2^0=1$.

Since it takes one additional step to reach $n=0$ and terminate, and since initially we may have $n>m$, it seems we may need up to $2k+2$ rounds.

Indeed, the desired bounds are not fully correct, as for example $m=1$, $n=42$ (so $k=0$) requires $2$ instead of just $2\cdot 0=0$ steps: $(1,42)\mapsto (42,1)\mapsto ({\bf 1},0)$.

*Remark:* A deeper analysis should exhibit that the behaviour is governed by powers of the golden ration $\phi\approx 1.618$ rather than $\sqrt 2\approx 1.414$.

This is just an informal sketch but might be useful.

In each step you’re dividing either by m (i.e. what’s left from it) or by n (i.e. what’s left from it). Both of them are >= 2 (as you’re still dividing to them). So each time you’re dividing at least by 2. The algorithm stops when you reach 1. So … it’s obvious that you can’t divide more than k times i.e. do more than k steps (if you do more than k it would mean one of the numbers becomes 1 or smaller than 1, and you continue the algorithm, which is not possible).

- Applications of the p-adics
- (USAJMO)Find the integer solutions:$ab^5+3=x^3,a^5b+3=y^3$
- Schur skew functions
- How to evaluate $I=\displaystyle\int_0^{\pi/2}x^2\ln(\sin x)\ln(\cos x)\ \mathrm dx$
- A circle has the same center as an ellipse and passes through the foci $F_1$ and $F_2$ of the ellipse, two curves intersect in $4$ points.
- Do there exist bounded operators with unbounded inverses?
- 2 Tricks to prove Every group with an identity and x*x = identity is Abelian – Fraleigh p. 48 4.32
- Pushforward of Lie Bracket
- Optimization by Symmetry?
- Intermediate fields of cyclotomic splitting fields and the polynomials they split
- Why is the condition enough for a matrix to be diagonalizable?
- Finding the shortest distance between two lines
- Is $$ a countable disjoint union of closed sets?
- What are cohomology rings good for?
- Zariski topology irreducible affine curve is same as the cofinite topology