Generalized Pépin-Test (Problem understanding a paper)

Question

I am reading this paper (but you don't need to, I will write down what is needed for the question), and I have difficulty understanding a certain conclusion.

$(1.1)\ \ $ $n = 2^k+1$ is prime $\Leftrightarrow$ $3^{\frac{n-1}{2}}\equiv -1 \pmod n.$

I totally understand this, the Pépin-Test.

The paper raises the problem

Problem $(2.3)$. Given an odd integer $h > 1$. Determine a finite set $\mathfrak{D}$ and for every positive integer $k \geq 2$ an integer $D\in \mathfrak{D}$ such that $\left(\frac{D}{h\cdot 2^k+1}\right) \neq 1$ and $D\not\equiv 0 \pmod{h\cdot 2^k+1}$.

where$\left(\frac{\cdot}{\cdot}\right)$ is the Jacobi-Symbol. I do understand this problem.

Later, the author claims

$(3.1)\quad$ Let $n=h\cdot 2^k+1$ with $h\not\equiv 0\pmod 3$, $k\geq 2$. Then $\mathfrak{D}=\{3\}$ and $D_k = 3$ for $k\geq 2$ solves $(2.3)$. In particular, If $2^k>h$, then $n$ is prime $\Leftrightarrow 3^{\frac{n-1}{2}}\equiv -1 \pmod n$.

I could prove this, also.

Now comes my question. The author says

The first observation we make is that a solution to Problem $(2.3)$ for one particular $h$ will in general lead to a solution for every $h'$ in the same residue class modulo $\prod\limits_{D\in\mathfrak{D}}D$. In that light, $(3.1)$ is in fact a consequence of $(1.1)$ and the special case $h = 5$ and $\mathfrak{D} = \{3\}$.

I don't know how to handle this sentence. Unfortunately, I don't understand the special case. So, $\prod\limits_{D\in\mathfrak{D}}D = 3$, still. But the residue classes $5\pmod 3$ are $-4,-1,2,5,8...$ and so on. But $\prod\limits_{D\in\mathfrak{D}}D = 3$ also solves $h \equiv 1,4,7...$.

I know that in my case $\left(\frac{D}{h\cdot 2^k + 1}\right)$ is the same as $\left(\frac{-D}{h\cdot 2^k + 1}\right)$, so I could come up with that. But I think this is not what the sentence wants to express. I do not understand this claim.

Answer 1

Let us introduce Problem $(2.3')$.

Problem $(2.3')$. Given an odd integer $h > 1$. Determine a finite set $\mathfrak{D}$, an integer $\ell\ge2$ and for every positive integer $k \geq l$ an integer $D\in \mathfrak{D}$ such that $\left(\frac{D}{h\cdot 2^k+1}\right) \neq 1$ and $D\not\equiv 0 \pmod{h\cdot 2^k+1}$.

Claim: If we have solved problem $(2.3')$ for $h$, then we can solve problem $(2.3)$ for $h$ as well.
Proof: Suppose we have $h, \mathfrak D, \ell$ and $k\to D$ as prescribed in $(2.3')$. There are only finitely many integers $k$ such that $2\le k<\ell$. For each such $k$, choose $$a_{h,k}=\begin{cases} \text{a positive non-quadratic residue of }h\cdot2^k+1&\text{ if }h\cdot 2^k+1\text{ is prime}\\ \text{a prime factor of } h\cdot 2^k+1 &\text{ if }h\cdot 2^k+1\text{ is not prime}\\ \end{cases}$$ Then $h, \mathfrak D\cup\{a_{h,k}\mid 2\le k<\ell\}$, $k\to\begin{cases}a_{h,k}&\text{ if } 2\le k< l\\D&\text{ if } k\ge\ell\end{cases}$ can be used for problem $(2.3)$.

---

The first observation we make is that a solution to Problem $(2.3)$ for one particular $h$ will in general lead to a solution for every $h'$ in the same residue class modulo $\prod\limits_{D\in\mathfrak{D}}D$.

Suppose for a particular odd integer $h > 1$, we have found a solution to Problem $(2.3)$, i.e., a finite set $\mathfrak{D}_h$ and for every positive integer $k \geq 2$ an integer $D_{h,k}\in \mathfrak{D}_h$ such that $\left(\frac{D_{h,k}}{h\cdot 2^k+1}\right) \neq 1$ and $D_{h,k}\not\equiv 0 \mod{h\cdot 2^k+1}$.

Suppose we have another odd integer $h'>1$ such that $h'\equiv h \bmod(\prod\limits_{d\in\mathfrak D_h}d)$. I use letter $d$ instead of $D$ as the dummy index variable in the product so as to avoid the abuse of letter $D$. Of course, $\prod\limits_{d\in\mathfrak D_h}d$ and $\prod\limits_{D\in\mathfrak D_h}D$ mean the same number.

In order to show that we can find a solution of $(2.3)$ for $h'$ as well, it is enough to show that we can find a solution of $(2.3')$ for $h'$, thanks to the claim above.

Let $\mathfrak{D}_{h'}=\mathfrak D_h$, $\ell=\lceil\displaystyle{\log_2\left(\frac{\max_{d\in\mathfrak D_{h}}d}{h'}\right)}\rceil$ and for every positive integer $k\ge\ell$, $D_{h',k}=D_{h,k}$.

• $D_{h',k}\in \mathfrak{D}_{h'}$

• We have $$\begin{align}\left(\frac{D_{h',k}}{h'\cdot 2^k+1}\right) &= \left(\frac{h'\cdot 2^k+1}{D_{h',k}}\right)\tag{1a}\\ &= \left(\frac{h'\cdot 2^k+1}{D_{h,k}}\right)\tag{1b}\\ &= \left(\frac{h\cdot 2^k+1}{D_{h,k}}\right)\tag{1c}\\ &= \left(\frac{D_{h,k}}{h\cdot 2^k+1}\right)\tag{1d}\\ &\neq 1\tag{1e}\end{align}$$ Explanations:
  $(1a)$: Since $k\ge2$, $h'\cdot2^k+1\equiv1\mod4$. Apply the law of quadratic reciprocity for Jacobi symbol.
  $(1b)$: $D_{h',k}=D_{h,k}$.
  $(1c)$: Since $h'\equiv h \bmod\prod\limits_{d\in\mathfrak D_h}d$, we have $h'\cdot 2^k+1\equiv h\cdot 2^k+1\bmod\prod\limits_{d\in\mathfrak D_h}d$. Since $D_{h,k}\in \mathfrak D_h$, $h'\cdot 2^k+1\equiv h\cdot 2^k+1\bmod D_{h,k}$
  $(1d)$: Similar to $(1a)$.
  $(1e)$: Assumption.

• $0<D_{h',k}\le\displaystyle{\max_{d\in\mathfrak D_{h}}d} \le h'\cdot 2^\ell< h'\cdot 2^k+1.$

  Hence $D_{h',k}\not\equiv 0 \mod{h'\cdot 2^k+1}$.

---

... $(3.1)$ is in fact a consequence of $(1.1)$ and the special case $h = 5$ and $\mathfrak{D} = \{3\}$

$(1.1)$ is the special case of $(3.1)$ with $h=1$.

"the special case $h = 5$ and $\mathfrak{D} = \{3\}$" refers to the special case of $(3.1)$ with $h=5$.

In other words, $(3.1)$ is the consequence of two special cases of itself. A clearer statement could have been

... $(3.1)$ is in fact a consequence of two special cases of itself, the case $h=1$, which is $(1.1)$ and the case $h = 5$.