I came to this question in the Problem Solving Strategies.
We start with the state $(a,b)$ where $a,b$ are positive integers. To this initial sate we apply the following algoritm
While $a>0$, do if $a<b$ then $(a,b)\rightarrow (2a,b-a)$ else $(a,b)\rightarrow (a-b,2b)$
. For which starting position does the algortim stops?In how many step does it stops if it stops?
The solution presented in the book.
Here is a solution valid for natural, rational and irrational numbers.With the invariant a + b=n the algorithm can be reformulated as follows:
If $a < n/2$, replace $a$ by $2a$. If $a ≥ n/2$, replace $a$ by $a − b=$ $a − (n − a) = 2a − n ≡ 2a (mod\ n)$. Thus, we double $a$ repeatedly modulo n and get the sequence
$a, 2a, 2^2a, 2^3a, . . . (mod\ n).$
Divide $a$ by $n$ in base 2. There are three cases.
(a) The result is terminating:
$a/n=0.d_1d_2d_3 . . . d_k, di ∈ {0, 1}$.Then $2k ≡ 0(mod\ n)$ but $2^i !≡0$ (mod n) for i < k. Thus, the algorithm stops after exactly k steps.
(b) The result is nonterminating and periodic.
$a/n= 0.a_1a_2 . . . a_pd_1d_2 . . . d_kd_1d_2 . . . d_k . . . .$
The algorithm will not stop, but the sequence (1) has period k with tail p.
(c) The result is nonterminating and nonperiodic: $a/n= 0.d_1d_2d_3 . . ..$ In this case, the algorithm will not stop, and the sequence (1) is not periodic.
I understood it till the point "we double $a$ repeatedly modulo n.." and why division is being done in base 2. I am not able to understand the argument ahead how $2^k$ is 0 mod n and how does it implies that algorithm will stop after k steps and so on
The algorithm terminates iff one of the numbers turns $0$. Since we defined $n$ as $a+b$, which stays invariant throughout the algorithm, the numbers in the end must be $0$ and $n$, both of which are $0$ modulo $n$ if the algorithm terminates. On the other hand, assume that the numbers you get in one step of the algorithm are $0$ modulo $n$ (if one is $0$ modulo $n$, the other must be as well). Then, since the numbers add to $n$ and both cannot be $\geqslant n$, one of them must be $0$. Hence, all you need to find is whether one of the numbers ever turns $0$ modulo $n$. This is exactly what is being done.
The values of the first number modulo $n$ follows the sequence $2^ia$ where $i=0,1,2,\cdots$ and we want to see when $n \mid 2^ia$. Equivalently, we want to know if there exists some $2^i$ which when multiplied with $\frac{a}{n}$ produces an integer. This is why we moved to base $2$, such a value $2^i$ exists if and only if $\frac{a}{n}$ is terminating in base $2$, with the least value of $i$ being the number of bits after the ones place.