Intereting Posts

L-functions identically zero
A ring that is not a Euclidean domain
Does $\frac{nx}{1+n \sin(x)}$ converge uniformly on $$ for all $a \in (0,\pi/2]$?
Showing diffeomorphism between $S^1 \subset \mathbb{R}^2$ and $\mathbb{RP}^1$
Numbers that are the sum of the squares of their prime factors
Why do the even Bernoulli numbers grow so fast?
Find number of integral solutions of $\sqrt{n}+\sqrt{n+7259}$
Quotient ring of Gaussian integers $\mathbb{Z}/(a+bi)$ when $a$ and $b$ are NOT coprime
Visually deceptive “proofs” which are mathematically wrong
I need to find all functions $f:\mathbb R \rightarrow \mathbb R$ which are continuous and satisfy $f(x+y)=f(x)+f(y)$
Do “other” trigonometric functions than Tan Sin Cos and their derivatives exist?
Why are measures real-valued?
Let $A$ and $B$ be $n \times n$ real matrices such that $AB=BA=0$ and $A+B$ is invertible
Is there a field $F$ which is isomorphic to $F(X,Y)$ but not to $F(X)$?
Does an uncountable discrete subspace of the reals exist?

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.

- Visualizing tuples $(a,b,x,y)$ of the extended Euclidean algorithm in a four-dimensional tesseract. Are there hidden symmetries?
- Euclidean Algorithm help!
- The ring $\mathbb Z= \{a+b\sqrt{-2} ; a\in \mathbb Z,b\in \mathbb Z \}$ has a Euclidean algorithm
- Linear diophantine equation $100x - 23y = -19$
- Have I found an example of norm-Euclidean failure in $\mathbb Z $?
- 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$ …
- Generalisation of euclidean domains
- Bezout's Theorem
- Extended Euclidean Algorithm, what is our answer?
- 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).

- Improper integral of $\frac{x}{e^{x}+1}$
- How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?
- Using residues to evaluate a sum involving the square of $\text{csch}$
- Thue-Morse sequence cube-freeness proof from the Book
- Fluids Euler's Equation
- Let $Z$ be standard normal can we find a pdf of $(Z_1,Z_2)$ where $Z_1=Z \cdot 1_{S},Z_2=Z \cdot 1_{S^c}$
- Smallest integer divisible by all up to $n$
- Does $|x^G|$ divide the order $\langle x^G\rangle$?
- regularity of the solution for the heat equation on half space with boundary condition specified
- What is the motivation for semidirect products?
- How can I calculate the limit of exponential divided by factorial?
- Length of period of decimal expansion of a fraction
- zero of vector field with index 0
- Do these matrix rings have non-zero elements that are neither units nor zero divisors?
- How to show that $m^*(A \cup B) + m^*(A \cap B) \leq m^*(A)+m^*(B)$ for any $A,B \subseteq \mathbb{R}$?