The divisibility problem

Question

I am interested in solving a problem from number theory.

$\textbf{Formulation:}$

Is it true that if $2k +1$ is a divisor of $2n+1$, then each of the numbers $2^{2n +1} \pm 2^{n+1} +1$ is divided by exactly one of the numbers $2^{2k + 1} \pm 2^{k+1} + 1?$

I mean, can't it be that $2^{2k+1} + 2^{k+1}+1$ and $2^{2k+1} - 2^{k+1}+1$ will simultaneously divide $2^{2n +1} +2^{n+1} +1$ or $2^{2n+1} - 2^{n+1} +1$.

I know how to prove the fact that the numbers $2^{2k+1}\pm 2^{k+1}+1$ should divide $2^{2n+1}\pm 2^{n+1}+1$, but I don't know how to solve the problem I described.

(This is due precisely to the fact that the order of these groups is the order of the Hall subgroups $A_i$ in the group $Sz(q), q = 2^{2n+1}$ and its subfield subgroup $Sz(q_0)\; (q_0 = 2^{2k+1})$. It is clear that cyclic groups of the order $2^{2k+ 1}\pm 2^{k+1}+ 1$ will be contained in one of the cyclic subgroups $A_i$ (because they have nowhere else to be contained, based on the list of Suzuki subgroups). So their order will also divide the orders of $A_i$, which is $2^{2n+1}\pm 2^{n+1}+1$).

Any help? I will be very grateful for any help in the solution.

Answer 1

As used in the AoPS thread Number Theory, for any non-negative integer $x$, with $f_{x+} = 2^{2x+1} + 2^{x+1} + 1$ and $f_{x-} = 2^{2x+1} - 2^{x+1} + 1$, we get

$$\begin{equation}\begin{aligned} m_x & = f_{x+}f_{x-} \\ & = ((2^{2x+1}+1) + 2^{x+1})((2^{2x+1}+1) - 2^{x+1}) \\ & = (2^{2x+1}+1)^2 - (2^{x+1})^2 \\ & = 2^{4x+2} + 2(2^{2x+1}) + 1 - 2^{2x+2} \\ & = 4^{2x+1} + 2^{2x+2} + 1 - 2^{2x+2} \\ & = 4^{2x+1} + 1 \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

With $4^{2k+1} \equiv -1 \pmod{m_k}$, then since $2k+1$ divides $2n+1$, with both being odd, we have $4^{2n+1} \equiv -1 \pmod{m_k}$ as well, so \eqref{eq1A} gives that $m_{k} \mid m_{n}$ (as you have also indicated).

Next, $\gcd(f_{k+}, f_{k-}) = 1$ (as the $\gcd$ must divide their difference, i.e., $2^{k+2}$, so it must be $1$ as both values are odd). To check the correctness of your formulation, first note that for $k=0$, since $f_{0-} = 2^{1} - 2^{1} + 1 = 1$, then $m_{k}$ actually divides one of $f_{n-}$ and $f_{n+}$. Thus, only consider $k \gt 0$. As $2k + 1$ is a divisor of $2n + 1$, and both are odd integers, then

$$2n+1 = (8i + j)(2k+1), \; i \in \mathbb{Z},\; i \ge 0, \; j \in \{1, 3, 5, 7\} \tag{2}\label{eq2A}$$

From \eqref{eq2A}, we have

$$2n + 1 = 4i(4k+2) + j(2k + 1) \tag{3}\label{eq3A}$$

and also

$$\begin{equation}\begin{aligned} 2n + 2 & = 4i(4k+2) + 2jk + j + 1 \\ n + 1 & = 2i(4k+2) + jk + \frac{j+1}{2} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

Since \eqref{eq1A} gives that $2^{2i(4k+2)} \equiv \left(4^{2k+1}\right)^{2i} \equiv 1 \pmod{m_{k}}$, we then get

$$2^{2n+1}\pm 2^{n+1}+1 \equiv 2^{j(2k+1)} \pm 2^{jk + \frac{j+1}{2}} + 1 \pmod{m_k} \tag{5}\label{eq5A}$$

We now need to check if the modulo value for $f_{n+}$ is coprime to $f_{k+}$ or $f_{k-}$, and similarly for $f_{n-}$. For $j = 1$, \eqref{eq5A} becomes

$$2^{2n+1}\pm 2^{n+1}+1 \equiv 2^{2k+1} \pm 2^{k+1} + 1 \pmod{m_{k}} \tag{6}\label{eq6A}$$

Due to $f_{k+}$ and $f_{k-}$ being coprime, this shows $f_{k+}\mid f_{n+}$ and $f_{k-}\mid f_{n-}$ only. Next, with $j = 3$, we have

$$\begin{equation}\begin{aligned} 2^{2n+1}\pm 2^{n+1}+1 & \equiv 2^{6k+3} \pm 2^{3k+2} + 1 \\ & \equiv 2^{4k+2}(2^{2k+1}) \pm 2^{3k+2} + 1 \\ & \equiv -2^{2k+1} \pm 2^{3k+2} + 1 \\ & \equiv 2^{2k+1}(\pm 2^{k+1} - 1) + 1 \pmod{m_k} \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

For checking $f_{n+}$ with $f_{k+}$, we have

$$\begin{equation}\begin{aligned} 2^{2k+1}(2^{k+1}-1) + 1 & \equiv (-2^{k+1}-1)(2^{k+1}-1) + 1 \\ & \equiv -2^{2k+2} + 2 \\ & \equiv -2(2^{2k+1}-1) \\ & \equiv -2(-2^{k+1}-2) \\ & \equiv 4(2^{k}+1) \pmod{f_{k+}} \end{aligned}\end{equation}\tag{8}\label{eq8A}$$

However, with $2^{k}\equiv -1\pmod{2^{k}+1}$, we get $f_{k+}\equiv 2 - 2 + 1 \equiv 1\pmod{2^{k}+1}$. Thus, $\gcd(f_{k+},f_{n+}) = 1$, so we must have $f_{k-}\mid f_{n+}$ instead (to confirm, note we get $(2^{k+1} - 1)^2 + 1 \equiv 2(2^{2k+1} - 2^{k+1} + 1) \equiv 0 \pmod{f_{k-}}$). Similarly, to check $f_{n-}$ with $f_{k-}$, we get

$$\begin{equation}\begin{aligned} 2^{2k+1}(-2^{k+1}-1) + 1 & \equiv (2^{k+1}-1)(-2^{k+1}-1) + 1 \\ & \equiv -2^{2k+2} + 2 \\ & \equiv -2(2^{2k+1}-1) \\ & \equiv -2(2^{k+1}-2) \\ & \equiv -4(2^{k}-1) \pmod{f_{k-}} \end{aligned}\end{equation}\tag{9}\label{eq9A}$$

With $2^{k} \equiv 1 \pmod{2^{k}-1}$, then $f_{k-} \equiv 2 - 2 + 1 \equiv 1 \pmod{2^{k}-1}$, so this shows $\gcd(f_{k-}, f_{n-}) = 1$. Thus, we must have $f_{k+}\mid f_{n-}$ only instead. Next, using $j = 5$ in \eqref{eq5A} gives that

$$\begin{equation}\begin{aligned} 2^{2n+1}\pm 2^{n+1}+1 & \equiv 2^{10k+5} \pm 2^{5k+3} + 1 \\ & \equiv 2^{2(4k+2)}(2^{2k+1}) \pm 2^{4k+2}(2^{k+1}) + 1 \\ & \equiv 2^{2k+1} \mp 2^{k+1} + 1 \pmod{m_k} \end{aligned}\end{equation}\tag{10}\label{eq10A}$$

This is basically the same as \eqref{eq6A}, but with the signs switched, so a similar conclusion holds (with it being $f_{k-}\mid f_{n+}$ and $f_{k+}\mid f_{n-}$ only instead). Finally, with the $j = 7$ possibility in \eqref{eq5A},

$$\begin{equation}\begin{aligned} 2^{2n+1}\pm 2^{n+1}+1 & \equiv 2^{14k+7} \pm 2^{7k+4} + 1 \\ & \equiv 2^{3(4k+2)}(2^{2k+1}) \pm 2^{4k+2}(2^{3k+2}) + 1 \\ & \equiv -2^{2k+1} \mp 2^{3k+2} + 1 \pmod{m_k} \end{aligned}\end{equation}\tag{11}\label{eq11A}$$

Since this is \eqref{eq7A}, but with the signs switched, we get that $f_{k+}\mid f_{n+}$ and $f_{k-}\mid f_{n-}$ only.

In conclusion, this confirms your formulation is true for $k \gt 0$, i.e.,

... each of the numbers $2^{2n +1} \pm 2^{n+1} +1$ is divided by exactly one of the numbers $2^{2k + 1} \pm 2^{k+1} + 1$

Answer 2

For $k=0$, no. Other than that, yes.

If $k=0$ (and so $2k+1=1$ is always a divisor of $2n+1$), then there are easy counterexamples: for example, if $n=3$, $2^{2n+1}+2^{n+1}+1=145$ is divisible by both $2^1+2^1+1=5$ and $2^1-2^1+1=1$. For the rest of this answer I will assume $k \neq 0$.

If a number is divisible by both of $2^{2k+1} \pm 2^{k+1} + 1$ then it is also divisible by their product, which is $(2^{2k+1}+2^{k+1}+1)(2^{2k+1}-2^{k+1}+1)$. Expanding this (difference of squares) we get $(2^{2k+1}+1)^2-2^{2k+2} = 2^{4k+2}+2^{2k+2}+1-2^{2k+2}=2^{4k+2}+1$.

Now consider $2^{2n+1}\pm 2^{n+1}+1$ modulo $2^{4k+2}+1$. We can eliminate the $2^{2n+1}$ by subtracting $2^{2n+1-4k-2}(2^{4k+2}+1)$, replacing it with $2$ to the power of an exponent that is $4k+2$ less (and also negating it). If we keep doing this, eventually it will stop working because the exponent is less than $4k+2$; more precisely, it will be the remainder when $2n+1$ is divided by $4k+2$, which is $2k+1$ (it can't be $0$, and it must be divisible by $2k+1$). Now we have $\pm 2^{n+1}\pm 2^{2k+1}+1$ ($\pm$ to account for having negated it an unknown number of times).

If $2k+1$ divides $n+1$, then because it divides $2n+1$, it must also divide $1$, so it is $1$, and $k = 0$, which is the case in the first paragraph; so $2k+1$ does not divide $n+1$. We can reduce the $2^{n+1}$ term the same way as the previous paragraph, and end up with the remainder of $n+1$ divided by $4k+2$. This can't be $0$ or $2k+1$ (otherwise $2k+1$ would divide $n+1$), so we have the sum of three distinct powers of $2$ (with $\pm$s, and viewing $1$ as $2^0$), with all of the exponents less than $4k+2$. This has an absolute value less than $2^{4k+2}+1$, and is also not $0$, therefore it is not divisible by $2^{4k+2}+1$, so the number we started with isn't either.