I'm reading Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh and trying to understand the proof of the Fact 1 on page 3.
Fact 1: Let $(N,e)$ be an RSA public key. Given the private key $d$, one can efficiently factor the modulus $N = pq$.
Dan says that since $\phi(N)=(p-1)(q-1)$ is even, $k=de-1=2^t r$ with $r$ odd and $t\geq1$. $k$ is a multiple of $\phi(N)$. Well, I tried to derive that formula for $k$, but didn't succeed. Any ideas?
The condition $de \equiv 1 \mod \phi(N)$ can also be written as $$ de - 1 = k = m\phi(N) $$ with some integer $m$. Now $\phi(N)$ is divisible by 4 since $p-1$ and $q-1$ are both even, hence $k$ is divisible by 4. Keep dividing $k$ by 2 until you get an odd quotient. Then $k = 2^tr$ with $t \ge 2$ and odd $r$.