How to prove these two ways give the same numbers? How to prove these two ways give the same numbers?
Way 1:
Step 1 : 73 +  1 =  74. Get the odd part of  74, which is 37    
Step 2 : 73 + 37 = 110. Get the odd part of 110, which is 55
Step 3 : 73 + 55 = 128. Get the odd part of 128, which is  1

Continuing this operation (with 73 + 1) repeats the same steps as above, in a cycle.
Way 2:  
Step 1:  (2^x) * ( 1/73) > 1 (7 is the smallest number for x)
(2^7) * ( 1/73) - 1 = 55/73

Step 2:  (2^x) * (55/73) > 1 (1 is the smallest number for x)
(2^1) * (55/73) - 1 = 37/73

Step 3:  (2^x) * (37/73) > 1 (1 is the smallest number for x)
(2^1) * (37/73) - 1 =  1/73

Repeating the steps with the fraction 1/73 goes back to step 1, and repeats them in a cycle.
The two ways have the same numbers $\{1, 37, 55\}$ in the 3 steps. How can we prove that the two ways are equivalent and give the same number of steps?
 A: Let $M=37$ (or any odd prime for that matter).
To formalize your first "way":
You start with an odd number $a_1$ with $1\le a_1<M$ (here specifically: $a_1=1$) and then recursively let $a_{n+1}=u$, where $u$ is the unique odd number such that $M+a_n=2^lu$ with $l\in\mathbb N_0$.
By induction, one finds that $a_n$ is an odd integer and $1\le a_n<M$
To formalize your second "way":
You start with $b_1=\frac c{M}$ where $1\le c<M$ is odd (here specifically: $c=1$) and then recursively let $b_{n+1}=2^kb_n-1$ where $k\in\mathbb N$ is chosen minimally with $2^kb_n>1$.
Clearly, this implies by induction that $0< b_n\le 1$ and $Mb_n$ is an odd integer for all $n$.
Then we have
Proposition. If $a_{m+1}=M b_n$, then $a_m=M b_{n+1}$.
Proof: 
Using $b_{n+1}=2^kb_n-1$, $M+a_m=2^la_{m+1}$, and  $a_{m+1}=M b_n$, we find
$$Mb_{n+1}=2^kMb_n-M = 2^ka_{m+1}-M=2^{k-l}(a_m+M)-M.$$
If $k>l$, we obtain that $Mb_{n+1}\ge 2a_m+M>M$, contradicting $b_{n+1}\le 1$.
And if $k<l$, we obtain $Mb_{n+1}\le \frac12 a_m-\frac 12 M<0$, contradicting $b_{n+1}>0$. Therefore $k=l$ and
$$ Mb_{n+1} = a_m$$
as was to be shown. $_\square$
Since there are only finitely many values available for $a_n$ (namely the odd naturals below $M$), the sequence $(a_n)_{n\in \mathbb N}$ must be eventually periodic, that is, there exists $p>0$ and $r\ge1$ such that $a_{n+p}=a_n$ for all $n\ge r$. Let $r$ be the smallest natural making this true. If we assume $r>1$, then  by chosing $c=a_{r-1+p}$ in the definition of the sequenc $(b_n)_{n\in\mathbb N}$ we can enforce $Mb_1=a_{r-1+2p}=a_{r-1+p}$ and with the proposition find $Mb_2=a_{r-1+p}=a_{r-1}$ contradicting minimality of $r$. We conclude that $r=1$, that is the sequence $(a_n)_{n\in\mathbb N}$ is immediately periodic.
Now the proposition implies that the sequence $(b_n)_{n\in\mathbb N}$ is also immediately periodic: Let $a_1=Mb_1$. Then by periodicity of $(a_n)$, we have $Mb_1=a_{1+p}$, by induction $Mb_k=a_{2+p-k}$ for $1\le k\le p+1$.
Especially, $b_{p+1}=b_1$ and hence by induction $b_{n+p}=b_n$ for all $n$.
Finally, we use the fact that $M$ is prime. Therefore the $Mb_n$ are precisely the numerators of the $b_n$. Our results above then show that these numerators are (if we start with $b_1=\frac{a_1}M$) precisely the same periodic sequence as $(a_n)$, but walking backwards. This is precisely what you observed.
EDIT: As remarked by miket, $M$ need only be odd but not necessarily prime. To see that, one must observe that the $a_n$ are always relatively prime to $M$ if one starts with $a_1$ relatively prime to $M$. Consequently, the $Mb_n$ are still the numerators of the $b_n$ (i.e. their denominators are $M$ in shortest terms).
