A conjecture about 433

Question

Motivated by Question 405105, I found the following

Conjecture. $2^{2n}-2^n+1 \equiv 0 \pmod {433}$ and $n=4m$ iff

$$\phi(m) = \phi(i + j) = \phi(i) + \phi(j) ,$$ and $$\phi(m) = \phi(ik) = \phi(i)\phi(k),$$

for some $i, j, k$, where $\phi$ is the Euler totient function.

Numerical computation indicates that it is true for $1≤m≤500$.

m = 3, 15, 21, 33, 39, 51, 57, 69, 75, 87, 93, 105, 111, 123, 129, 141, 147, 159, 165, 177, 183, 195, 201, 213, 219, 231, 237, 249, 255, 267, 273, 285, 291, 303, 309, 321, 327, 339, 345, 357, 363, 375, 381, 393, 399, 411, 417, 429, 435, 447, 453, 465, 471, 483, 489. 

See A306771 for details.

Question. Why 433? And how to prove "iff"?

ADDED

Noting $\phi(ik)=\phi(i)\phi(k)\frac{\gcd(i,k)}{\phi(\gcd(i,k))}$, we have

$$\phi(ik)=\phi(i)\phi(k) \iff \phi(\gcd(i,k))=\gcd(i,k)\iff\gcd(i,k)=1. $$

Answer 1

Since $2$ has multiplicative order $72$ modulo $433$, it is easy to check with a quick computation that $2^{2n}-2^n+1\equiv 0\pmod{433}$ holds iff $n\equiv\pm 12\pmod{72}$, or $m\equiv\pm 3\pmod{18}$. In particular, $m$ is divisible by $3$, say $m=3l$, and $l$ is odd and not divisible by $3$. Therefore for $i=l,j=2l$ and $k=3$ we have $\phi(m)=\phi(3l)=2\phi(l)$ while $\phi(i)=\phi(l),\phi(j)=\phi(2l)=\phi(l),\phi(k)=2$, making the equalities in the conjecture true.

As for why $433$ - I suspect it is just a numerical coincidence which happens to capture $m$ modulo $18$.

Answer 2

The "if" part depends on non-existence of an integer $k\equiv2\pmod3$ satisfying $\phi(k)=\frac{k+1}2$, which I believe is an open question. The currently known solutions to $\phi(k)=\frac{k+1}2$ are listed in OEIS A050474.

Indeed, from $$\phi(i)\phi(k)=\phi(m)=\phi(i)+\phi(m-i)=\phi(i)+\phi(i(k-1)),$$ it follows that $\phi(i)\mid \phi(i(k-1))$ and $$\phi(k)=1+\frac{\phi(i(k-1))}{\phi(i)}.$$

We have with necessity $k\geq 3$ and thus $\phi(k)$ is even. Then $\frac{\phi(i(k-1))}{\phi(i)}$ is odd, implying that for every odd prime $p\mid (k-1)$ we have $p\mid i$, and $2\mid (k-1)$ only if $2\nmid i$.

So, if $i$ is even, or if both $i$ and $k-1$ are odd, then $\phi(i(k-1))=\phi(i)(k-1)$ and thus $\phi(k)=k$, giving only extraneous value $k=1$.

In the remaining case of odd $i$ and even $k-1$, we have $\phi(i(k-1))=\phi(i)\frac{k-1}2$ and thus $\phi(k)=\frac{k+1}2$. It can be seen that such $k$ must be squarefree.

Now, suppose we have fixed an odd integer $k>1$ satisfying $\phi(k)=\frac{k+1}2$. Then $m=ik$ will satisfy an original condition as soon as $i$ is odd, $\gcd(i,k)=1$, and $\mathrm{rad}(\frac{k-1}2)\mid i$. For example, when $k=15$, we need $\gcd(i,15)=1$ and $7\mid i$.

It remains to notice that if $3\mid k(k-1)$, then the corresponding solutions $m$ are included into those for $k=3$, i.e., $m\equiv 3,\ 15\pmod{18}$. Different solutions can be obtained only if we have $k\equiv2\pmod3$.

---

As for $433$, it can be replaced by any other prime, modulo which 2 has the multiplicative order 72. Such a prime must divide $\Phi_{72}(2)=433\times 38737$ as pointed out by @Wojowu. That is, the only other suitable prime is $38737$.