Problème de Znám

En théorie des nombres, le problème de Znám pose la question de déterminer les ensembles finis d'entiers strictement positifs ayant la propriété que tout élément de l'ensemble est un diviseur propre du produit des autres éléments de l'ensemble, plus 1. Le problème de Znám doit son nom au mathématicien slovaque Štefan Znám (1936–1993), qui le suggère en 1972, bien que d'autres mathématiciens envisagent des problèmes similaires à la même époque.

Les termes initiaux de la suite de Sylvester résolvent presque ce problème, sauf que le dernier terme choisi est égal à un plus le produit des autres, plutôt que d'être un véritable diviseur. Sun (1983) montre qu’il existe au moins une solution au (bon) problème de Znám pour tout $k\geqslant 5$. La solution de Sun est basée sur une récurrence similaire à celle de la suite de Sylvester, mais avec un ensemble de valeurs initiales différent.

Le problème du Znám est étroitement lié aux fractions égyptiennes. On sait qu’il n’existe qu’un nombre fini de solutions pour tout problème fixe $k$. On ne sait pas s'il existe des solutions au problème de Znám en utilisant uniquement des nombres impairs, et plusieurs autres questions restent ouvertes.

Énoncé du problème

Le problème de Znám pose la question de déterminer les ensembles finis d'entiers strictement positifs ayant la propriété que tout élément de l'ensemble est un diviseur propre du produit des autres éléments de l'ensemble, plus 1. En d'autres termes, étant donné $k$, on demande quels ensembles d'entiers strictement positifs :

$$\{n_{1},\ldots ,n_{k}\}$$

sont tels que, pour tout $i$, $n_{i}$ divise, sans lui être égal, le nombre :

$${\Bigl (}\prod _{j\neq i}^{n}n_{j}{\Bigr )}+1.$$

Un problème étroitement lié concerne les ensembles d'entiers pour lesquels tout entier de l'ensemble est un diviseur, mais pas nécessairement un diviseur propre, du produit des autres entiers de l'ensemble, plus 1. Ce problème ne semble pas avoir été nommé dans la littérature et sera appelé problème de Znám impropre. Toute solution au problème de Znám est également une solution au problème de Znám impropre, mais la réciproque n'est pas vraie.

Historique

Le problème de Znám doit son nom au mathématicien slovaque Štefan Znám, qui le suggère en 1972. Barbeau (1971) a posé le problème impropre de Znám pour $k=3$, et Mordell (1973), indépendamment de Znám, trouve toutes les solutions au problème impropre pour $k\leqslant 5$. Skula (1975) montre que le problème de Znám est insoluble pour $k<5$, et crédite J. Janák d'avoir trouvé la solution $\{2,3,11,23,31\}$ pour $k=5$ .

Exemples

La suite de Sylvester est une suite entière dont chaque terme est le produit des termes précédents plus 1. Les premiers termes de la suite sont 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 suite A000058 de l'OEIS.Les ensembles formés des premiers termes de la suite (tel que $\{2,3,7,43\}$) fournissent des solutions au problème de Znám impropre, mais pas au problème de Znám lui-même : tout élément de ces ensembles est un diviseur propre du produit des autres éléments plus 1, sauf le plus grand, qui est égal par définition au produit des autres plus 1.

$\{a=2,b=3,c=11,d=23,e=31\}$ est une solution au (bon) problème de Znám pour $k=5$ car :

$(bcde+1)/a=119543$

$(acde+1)/b=5229$

$(abde+1)/c=389$

$(abce+1)/d=89$

$(abcd+1)/e=49$

$\{2,3,7,47,395\}$ est la seule autre solution pour $k=5$.

Lien avec les fractions égyptiennes

Démonstration graphique du fait que ${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{11}}+{\frac {1}{23}}+{\frac {1}{31}}+{\frac {1}{2.13.11.23.31}}=1.$Chaque rangée de k carrés de longueur de côté 1/ k a une aire totale 1/ k, et tous les carrés réunis recouvrent exactement un carré plus grand d'aire égale à 1. La rangée inférieure de 47058 carrés dont le côté mesure 1/47058 est trop petite pour être visible sur la figure et n'est pas représentée.

On montre que toute solution $\{n_{1},\ldots ,n_{k}\}$ au problème de Znám impropre est telle que les entiers $n_{i}$ sont deux à deux premiers entre eux. Or, notant $N$ le produit des $n_{i}$, par définition, $n_{i}$ divise ${\frac {N}{n_{i}}}+1$ et divise ${\frac {N}{n_{j}}}$ pour $j\neq i$ donc divise ${\frac {N}{n_{1}}}+\cdots +{\frac {N}{n_{k}}}+1$. Le produit $N$ des $n_{i}$ divise donc ${\frac {N}{n_{1}}}+\cdots +{\frac {N}{n_{k}}}+1$, ce qui signifie que ${\frac {1}{n_{1}}}+\cdots +{\frac {1}{n_{k}}}+{\frac {1}{N}}$ est un entier.

Par exemple, pour $\{2,3,7,43\}$ on a ${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{11}}+{\frac {1}{23}}+{\frac {1}{31}}+{\frac {1}{2.3.11.23.31}}=1$.

Autrement dit toute solution au problème impropre de Znám fournit une solution à l'équation

$$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=y,$$

où $y$ ainsi que chaque $x_{i}$ est un entier strictement positif, et inversement, toute solution de ce type correspond à une solution du problème impropre de Znám. Cependant, toutes les solutions connues sont telles que $y=1$, donc satisfont l'équation

$$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1.$$

Autrement dit, elles conduisent à une représentation en somme de fractions égyptiennes du nombre 1. Plusieurs des articles cités sur le problème de Znám étudient également les solutions à cette équation. Brenton & Hill (1988) décrivent une application de l'équation en topologie, à la classification des singularités sur des surfaces, et Domaratzki et al. (2005) décrivent une application à la théorie des automates finis non déterministes.

Nombre de solutions

Le nombre de solutions au problème de Znám pour tout $k$ est fini, il est donc logique de dénombrer le nombre total de solutions pour chaque $k$ . Sun (1983) montre qu’il existe au moins une solution au (bon) problème de Znám pour tout $k\geqslant 5$. La solution de Sun est basée sur une récurrence similaire à celle de la suite de Sylvester, mais avec des valeurs initiales différentes. Le nombre de solutions pour les petites valeurs de $k$, commençant à $k=5$, forme la suite  :

2 , 5 , 18 , 96 (suite A075441 de l'OEIS).

Actuellement, on connait quelques solutions pour $k=9$ et $k=10$, mais on ne sait pas combien de solutions restent à découvrir pour ces valeurs de $k$. Cependant, il existe une infinité de solutions si $k$ n’est pas fixé : Cao & Jing (1998) montrent qu’il existe au moins 39 solutions pour tout $k\geqslant 12$, améliorant les résultats antérieurs prouvant l'existence de solutions  ; Sun & Cao (1988) supposent que le nombre de solutions croît de façon monotone avec $k$ .

On ne sait pas s'il existe des solutions au problème de Znám n'utilisant que des nombres impairs. À une exception près, toutes les solutions connues commencent par 2. Si tous les nombres d'une solution au problème de Znám ou au problème de Znám impropre sont premiers, leur produit est un nombre semi-parfait primaire  ; on ne sait pas s’il existe une infinité de solutions de ce type.

Voir aussi

• Nombre de Giuga
• Nombre semi-parfait primaire

Références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Znám's problem » (voir la liste des auteurs).

Sources

• G. E. J. Barbeau, « Problem 179 », Canadian Mathematical Bulletin, vol. 14, n^o 1,‎ 1971, p. 129.
• Lawrence Brenton et Richard Hill, « On the Diophantine equation ${\textstyle 1=\sum 1/n_{i}+1/\prod n_{i}}$ and a class of homologically trivial complex surface singularities », Pacific Journal of Mathematics, vol. 133, n^o 1,‎ 1988, p. 41–67 (DOI 10.2140/pjm.1988.133.41 , MR 0936356, lire en ligne).
• Lawrence Brenton et Ana Vasiliu, « Znám's problem », Mathematics Magazine, vol. 75, n^o 1,‎ 2002, p. 3–11 (DOI 10.2307/3219178, JSTOR 3219178).
• William Butske, Lynda M. Jaje et Daniel R. Mayernik, « On the equation ${\textstyle \sum _{p|N}{\frac {1}{p}}+{\frac {1}{N}}=1}$, pseudoperfect numbers, and perfectly weighted graphs », Mathematics of Computation, vol. 69,‎ 2000, p. 407–420 (DOI 10.1090/S0025-5718-99-01088-1 , MR 1648363, lire en ligne).
• Zhen Fu Cao et Cheng Ming Jing, « On the number of solutions of Znám's problem », J. Harbin Inst. Tech., vol. 30, n^o 1,‎ 1998, p. 46–49 (MR 1651784).
• Zhen Fu Cao, Rui Liu et Liang Rui Zhang, « On the equation ${\textstyle \sum _{j=1}^{s}(1/x_{j})+(1/(x_{1}\cdots x_{s}))=1}$ and Znám's problem », Journal of Number Theory, vol. 27, n^o 2,‎ 1987, p. 206–211 (DOI 10.1016/0022-314X(87)90062-X, MR 0909837).
• Michael Domaratzki, Keith Ellul, Jeffrey Shallit et Ming-Wei Wang, « Non-uniqueness and radius of cyclic unary NFAs », International Journal of Foundations of Computer Science, vol. 16, n^o 5,‎ 2005, p. 883–896 (DOI 10.1142/S0129054105003352, MR 2174328, lire en ligne).
• Jaroslav Janák et Ladislav Skula, « On the integers ${\textstyle x_{i}}$ for which ${\textstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1}$ », Math. Slovaca, vol. 28, n^o 3,‎ 1978, p. 305–310 (MR 0534998).
• L. J. Mordell, « Systems of congruences », Canadian Mathematical Bulletin, vol. 16, n^o 3,‎ 1973, p. 457–462 (DOI 10.4153/CMB-1973-077-3 , MR 0332650).
• Ladislav Skula, « On a problem of Znám », Acta Fac. Rerum Natur. Univ. Comenian. Math., vol. 32,‎ 1975, p. 87–90 (MR 0539862).
• Qi Sun, « On a problem of Š. Znám », Sichuan Daxue Xuebao, n^o 4,‎ 1983, p. 9–12 (MR 0750288).
• Qi Sun et Zhen Fu Cao, « On the equation ${\textstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n}$ and the number of solutions of Znám's problem », Northeastern Mathematics Journal, vol. 4, n^o 1,‎ 1988, p. 43–48 (MR 0970644).

Liens externes

• Primefan, « Solutions to Znám's Problem ».
• (en) Eric W. Weisstein, « Znám's Problem », sur MathWorld.