$n=pq$ with $p<q$ odd primes is there a fast way to determine if $p-1|q-1$ without knowing $p$ and $q$

Solution 1:

Let $n = pq$

if $p-1 \mid q-1$

1: $p-1 \mid n-1$

2: $q-1 \not\mid n-1$ (if this false, $n$ is a Carmichael number with 2 divisors)

3: $x^{n-1} = 1 \pmod p$ for any $x$ where $x$ is coprime with $n$ $\implies$ $x^n = x \pmod p$

So, we can do this steps:

Get random $x$ from $[0, n-1]$

Calculate $t = (x^n-x) \bmod n$. It is not $0$ with the probability about $\frac{\phi(q-1)}{q-1}$

$t=0 \pmod p$. So, greatest common divisor of $n$ and $t$ is $p$ if $p-1 \mid q-1$

So, if $\gcd \{\,n,t\,\}$ is $1$ - we can say "no".

if $\gcd \{\,n, t\,\} > 1$, we get the factorization and can check $p-1 \mid q-1$ manually