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

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.

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

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$$.

• Thank you for clearifying. So I was confused by the sentence itself, but I get this. What I still do not get is the meaning of "h' in the same residue class mod $\prod\limits_{D\in\mathfrak{D}}D$. So, let's say, for a fixed $h$ I have $\mathfrak{D} = \{3,5,7\}$. And $D$ works. Then $D$ works for $h' = h \pmod{3\cdot 5\cdot 7}$, too? Feb 14 at 8:35
• @mathquester Please check my updated answer. For a fixed $h$, $\mathfrak D_{h'}$ that we will construct may vary for different $h'\equiv h\bmod {\prod_{d\in\mathfrak D_h}d}$. Feb 14 at 22:37
• thank you for your time. I am working through your answer, yet I have some questions. So first of all, I showed that $\left(\frac{D}{n}\right) = 0 \Leftrightarrow gcd(D,n) > 1.$ So, for the test it would even be ok to get the result 0, because then I can conclude that $n$ is composite. I think you mean that with the case $h\cdot 2^k+1$ is not prime. But how do I choose an element $D$ wisely? I do not know whether $n$ is composite or prime. Let's say, I knew the prime decomposition of $h$. Then I only knew which $D$ is NOT to choose. Or do I miss something? Feb 15 at 17:09
• @mathquester Your comment is clear and correct to me until I read "How do I choose an element $D$ wisely...". Please tell me the first place in my answer that you do not understand yet. Feb 16 at 12:35
• My Problem is more general I think. I want an element $D$, such that $\left( \frac{h\cdot 2^k+1}{D}\right) = -1.$ Up to now I only know that I can't choose a divisor of $h$. So the question is. how do I find such an element less than "brute-force", i.e. trying the elements except the divisors of $h$. Feb 16 at 13:14