Find, without a computer program, all (odd) integers $x\leq 1000$ with $\gcd((x-1)/2, \phi(x)) $ being a nontrivial power of $2$ (i.e. a power of $2$ exceeding one).
There exist infinitely many odd composite integers $x$ with $\gcd((x-1)/2, \phi(x))$ not equal to a power of $2$. For instance, take $x=p^2$ with $p\equiv 3\mod 4$. Then $\gcd((x-1)/2 ,\phi(x)) = (p-1)\gcd((p+1)/2, p) = p-1.$ If $x=p^2$ with $p$ a prime equivalent to $1\mod 4$, then both $p^2 - p$ and $(p^2-1)/2$ are even and so the gcd is divisible by $2$. We have $\gcd(p^2 -p, (p^2-1)/2) = p-1$ as above,but this may not be a power of $2$. If instead $x=pq$ with $p\equiv 3\mod 4, q\equiv 3\mod 4$, then $\phi(x) = (p-1)(q-1),$ but I'm not sure if I can get a general formula for gcd. I know that $\phi(x) = \prod_{i=1}^k (p_i^{e_i} - p_i^{e_i-1})$ when $x= \prod_{i=1}^k p_i^{e_i}$ and each $p_i$ is a distinct prime.
If $x=p$ for a prime p, then $\gcd((x-1)/2, p-1) = (p-1)/2.$