# Recovering $\Phi(n)$ from a multiple?

I've been attending a series of lectures on Cryptography from an engineering perspective, which means that most of the assertions made are supplied without proof... here's one that the lecturer couldn't recall the reason for, nor original source of.

Given an unfactored $n=pq$, computing $\phi(n)$ is as hard as finding $p,q$; this is the key idea of various "RSA-like" cryptosystems. One presented had a step in which for a secret $k$ and a random $t$, $k-t\phi(n)$ is transmitted. The claim was then that this process should only be applied once, as if an attacker sees $k-t\phi(n)$ and $k-u\phi(n)$ then they can recover $(t-u)\phi(n)$, and it's alleged that this makes it easier to compute $\phi(n)$.

So my question is, why is it easier to compute $\phi(n)$ given a random multiple of it, assuming we're at "cryptographic size"? (that is, $p,q$ sufficiently large that it's not feasible to try and factor $n$ and $\phi(n)$)

If you know an even $m$ such that $a^m \equiv 1 \mod n, (a,n)=1$, e.g. a multiple of $\phi(n)$ then there is a standard probabilistic algorithm to factor $n=pq$. Write $m = 2^rs$ with $s$ odd. Pick a random $a$ and compute $a^s, a^{2s}, a^{4s},\ldots$. If $a^s \ne 1 \mod n$, then at some point in the calculation, you find $b \ne 1 \mod n$ with $b^2 \equiv 1 \mod n$. If $b \ne -1 \mod n$, then, as $b^2-1=(b-1)(b+1) \mod n$, you factor $n$ by computing $(b-1,n)$. This will succeed with probability $> 1/2$, so if it fails, pick another $a$. By picking enough $a$'s, you make the probability of success as close to $1$ as you like.