Chaîne de Cunningham

En mathématiques, une chaîne de Cunningham est une suite finie de nombres premiers vérifiant une certaine propriété. Les chaînes de Cunningham portent le nom du mathématicien indo-britannique Allan Cunningham (1842-1928).

Une chaîne de Cunningham de première espèce est une suite finie de nombres premiers ${\displaystyle (p_{1},\ldots ,p_{n})}$ telle que pour tout ${\displaystyle 1\leqslant i\leqslant n}$, ${\displaystyle p_{i+1}=2p_{i}+1}$. (Chacun des termes d'une telle chaîne excepté le dernier d'entre eux est un nombre premier de Sophie Germain). De manière similaire, une chaîne de Cunningham de deuxième espèce est une suite de nombres premiers ${\displaystyle (p_{1},\ldots ,p_{n})}$ tels que pour tout ${\displaystyle 1\leqslant i\leqslant n}$, ${\displaystyle p_{i+1}=2p_{i}-1}$.

Les chaînes de Cunningham se généralisent en les suites de nombres premiers ${\displaystyle (p_{1},\ldots ,p_{n})}$ telles que pour tout ${\displaystyle 1\leqslant i\leqslant n}$, ${\displaystyle p_{i+1}=ap_{i}+b}$ pour des entiers premiers entre eux fixés ${\displaystyle a,b}$ ; les chaînes résultantes sont appelées chaînes de Cunningham généralisées.

Une chaîne de Cunningham est dite complète si elle ne peut pas être étendue davantage, c'est-à-dire s'il n'existe aucun nombre premier qui pourrait suivre le dernier terme de la chaîne, ou précéder le premier.

Exemples de chaînes complètes de Cunningham du premier type :

${\displaystyle 2,5,11,23,47}$ (le nombre suivant serait ${\displaystyle 95}$ mais n'est pas premier).

${\displaystyle 3,7}$ (le nombre suivant serait ${\displaystyle 15}$ mais n'est pas premier).

${\displaystyle 29,59}$ (le nombre suivant serait ${\displaystyle 119=7\times 17}$ ).

${\displaystyle 41,83,167}$ (le nombre suivant serait ${\displaystyle 335}$).

${\displaystyle 89,179,359,719,1439,2879}$ (le nombre suivant serait ${\displaystyle 5759=13\times 443}$).

Exemples de chaînes complètes de Cunningham du deuxième type :

${\displaystyle 2,3,5}$ (le nombre suivant serait ${\displaystyle 9}$ mais n'est pas premier).

${\displaystyle 7,13}$ (le nombre suivant serait ${\displaystyle 25}$).

${\displaystyle 19,37,73}$ (le nombre suivant serait ${\displaystyle 145}$).

${\displaystyle 31,61}$ (le nombre suivant serait ${\displaystyle 121=11^{2}}$).

En 2018, la plus longue chaîne de Cunningham connue, de l'un ou l'autre type, comporte 19 nombres ; elle a été découverte par Jaroslaw Wroblewski en 2014^[1].

Si ${\displaystyle p_{1}>2}$, la longueur d'une chaine de Cunningham ${\displaystyle (p_{1},\ldots ,p_{n})}$ est inférieure ou égal à ${\displaystyle p_{1}-1}$; celle commençant par 2 étant finie, il n’existe donc pas de chaine de Cunningham infinie.

En effet, ${\displaystyle p_{i}=2^{i-1}p_{1}\pm (2^{i-1}-1)\,}$ (+ pour le premier type, - pour le deuxième) donc ${\displaystyle p_{i}\equiv \pm (2^{i-1}-1){\pmod {p_{1}}}}$. Mais d'après le petit théorème de Fermat (${\displaystyle p_{1}\neq 2}$) : ${\displaystyle 2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}}$, donc ${\displaystyle p_{1}}$ divise ${\displaystyle p_{p_{1}}}$ qui n'est donc pas premier.

• (en) The Prime Glossary : Cunningham chain sur les Prime Pages
• (en) Prime Links + + : Cunningham chains sur les Prime Pages
• (en) Suite  A005602 de l'OEIS : le plus petit nombre qui est le premier terme d'une chaîne complète de Cunnigham de première espèce de longueur ${\displaystyle n}$, pour ${\displaystyle 1\leqslant n\leqslant 16}$
• (en) Suite  A005603 de l'OEIS : le plus petit nombre qui est le premier terme d'une chaîne complète de Cunnigham de deuxième espèce de longueur ${\displaystyle n}$, pour ${\displaystyle 1\leqslant n\leqslant 16}$

• Arithmétique et théorie des nombres