Séminaire Delange-Pisot-Poitou.
Théorie des nombres

PAUL E RDÖS
Résultats et problèmes en théorie des nombres
Séminaire Delange-Pisot-Poitou. Théorie des nombres, tome 14, no 2 (1972-1973),
exp. no 24, p. 1-7.
<http://www.numdam.org/item?id=SDPP_1972-1973__14_2_A8_0>© Séminaire Delange-Pisot-Poitou. Théorie des nombres(Secrétariat mathématique, Paris), 1972-1973, tous droits réservés.
L’accès aux archives de la collection « Séminaire Delange-Pisot-Poitou. Théorie des nombres »implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php).
Toute utilisation commerciale ou impression systématique est constitutive d’une infraction
pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/

Séminaire DELANGE-PISOT-POITOU(Théorie des nombres)n°
14e année,

1972/73,24-01
21 mai 1973

24, 7 p.

RÉSULTATS ET PROBLÈMES EN THÉORIE DES NOMBRES
par Paul ERDÖS

Rédigé par Jean-Louis NICOLASrk(n) .

1. Un théorème de Van der Waerden et les fonctions

plus détaillée, d’autres références et d’autres conjectures, on

Pour une étude

22C~~224~

pourra voir ~ 10 ~ (p.
cles font le(p. 232). De façon générale, ces deux arti-

point sur plusieurs sujets de théorie des nombres et sont une mineinépuisable de conjectures et de problèmes ouverts. Comme autres recueils de problèmes, on pourra consulter aussi r 12~
VAN DER WAERDENadémontré le théorèmesuivant (cf. [32], C ~9 ~~ ~ 23~, et surtout~33~ où l’auteur expose le cheminement de son raisonnement dans sa découverte duthéorème).
~yTHEOREME. - Si l’on fait une
ses,partition de l’ensemble

Ndes entiers

endeux clas-quel que soit l’entier k, une au moins des deux classes contient une progres-sion arithmétique dektermes.

f(k) comme le plus petit entier tel que, si l’on partage les nombres 1 ~ n~ f(k) en deux classes arbitraires, l’une au moins contient une progression arithmétique de k termes. La majoration de f(k) est un problème diffiDéfinissons

cile, et la démonstration ae VAN DER WAERDEN donne une majoration par quelque chosedebeaucoup plus grand que

BERLEKAMP [4] a donné pourentiers

1 ~ n ~n,métique dek

k2k :f(k)en

f(k) ~ k2kla minoration

deux classes ne contenant

termes, à l’aide du corps fini à2kaucuneenpartageant les

progression arith-éléments.

Pour aborder la ma joration def(k), on est amené à la définition suivante.

Définition. - On désigne parrk(n)finievérifiantprogression arithmétique deUne famille deplus de1 ~ aikle nombre maximum de termes d’une suitea~ ...

rk(n)et ne contenant pas une

ntermes.

rk(n) nombres, tous plus petits que n , contient donc

forcément une progression arithmétique desavait démontrer

atktermes etsi, pour un certain

n/2 , cela donnerait pour f(k)la majorationn ,f(k)on.
n .

(pour cela, et pour d’autres pro-Propriété, .. On a r k ~n + n’) ~ r,(n) + r k (n’ ~cf. [~141)).
priétés élémentaires deBEHREND [~2~] a démontré l’existence deIla~"montré également que l’on avait"

ck=ck

=

pour tout

0k"

oubienSALEM [28] a démontré que

1 " . En 1942,(On peut obtenir une minoration simple der 3 ~n)constatant que la suite des0 et 2
avec uniquement les chiffresenqui s’écrivent dans la base 3
ne contient pas
trois termes en progression arithmétique). En 1946, BEHREND [3] anombresamélioré le résultat de SALEM en montrant :D’autre part,Enamajore

r 3 ~n~ obtenant :1968, SZEMEREDI [31], dans une démonstration compliquée, a montré que

Plusrécemment, dans un article à paraître aux Acta Arithmetica, il a démontré que

Conjecture 1. - Si l’on peut démontrerrk(n)cela entraînen(n)qu’il existe

k=nombre des nombres

nombrespremiers ~ n ,premiers formant une progression arithméti-que.

Exemple numérique. que de 10 termes.

199 + 210l

avec

90 l

est une progression arithméti-D’après A. SCHINZEL, le record serait une progression arithméti-

que de 16 nombres premiers.

Conjecture 2. - Si la suite infinie
sion arithmétique de 3 termes, alorsa2l/(a.)
03A3~i=1a~...

necontient pas une progres-conjecture de Goldbach(cf. PRACHAR, [22], p. 177) "tout nombre pair est somme de deux nombres premiers"
entraîne, pour un nombre premier p , que 2p = p? + Pô . CHOWLA [7] a démontré,
9sanshypothèse, qu’il existe une infinité de triplets de nombres premiers en pro-gression arithmétique, mais l’on aa1 a2telle que... ,où il est démontré

rapprochée deCette conjecture peut êtrean ~ a + a + ... + ani , vérifie I2014+oo .

Conjecture 3. - Soit f(n) une fonction quelconque detrer que, pour tout C , il existe d et m tels que :mieux, montrer qu’il existe une constanteouqu’une suite

Ndans(+1 , -l) . Mon-telle queclf(kd))1
partage les entiers en deux classes, et dire que
est grand signifie que la progression arithmétique
est située en grandepartie dans l’une des classes).
(La fonctiont~_~f(kd)Signalons enfin que, dans des travaux non publiés, DAVIES [Université de Leices-(Grande-Bretagno] avec l’hypothèse du continu, et BAUMGARTNER [Université deHanover, N. H. (Etats-Unis)] sans hypothèse, ont partagé les réels en deux parties,terdont l’une

contient pas une

neprogression arithmétique de 3 termes et l’autre neprogression arithmétique infinie.

contient pas une

2. Différence entre deux nombres premiers consécutifs.
Soitlepd = pn+ - pn . Pour une étuden-ième nombre premier. On poseplus détaillée de cette question, on pourra se reporter(p. 200 et suivantes),[11J (p. 222 et suivantes) et à C21~ ou [22] (chapitre V, § 5) .
Del’égalité

ü =1 d k p - p 1 .~=Le meilleur résultat

nité de valeurs deRANKIN [24]ré avec

CD’autre=n ,connu suronmontré avec

eY -ena,C

les grandes valeurs deposant log2(n)assezn131) donne pourT , la=dn

est: Pour une infi-log log n , etc.,

est la constante d’Euler.

ylaT

cemment montré que l’on peut prendre
Riemann donne, pouron déduit que= 2014 - e ; SCHÖNHAGE [30] et RANKIN [25] l’ ont amélio-part, on sait que, pour

MONTGOMERY [20] (p,log n ,nvaleur 1 2T=+ egrand, on a :très
Huxleyvaleur 3 Rappelons
5l’hypothèseaurait+ e .

£(cf.

ré-quedePRACHAR 1221, p.

320-324) et que+ e .

CRAXER a conjecturé

Pour lespetites valeurs dedn , la conjecture la plus probable est l’existenced’une infinité de nombres premiers jumeaux, i. e.
limd 2 . Le meilleur résul=tat est dû à BOHBIERI et DAVENPORT

P.

Commelim d([5] voir aussi [9]) qui démontrentadémontré que=+ co ~ il existe une infinité de~ntels que

TURAN [17] ont montré qu’il existe une infinité deetn

Conjecture 3. - Existe-t-il une infinité den

Conjecture 4. - Y a-t-il une infinité detels quend>n+~tels quedERDOSd.n>

ndn+1.

tels que

Conjecture 5.( primée 500 francs, et entrainée par la conjecture 3 ou la con jec-.

4). - Montrer qu’il n’existe pas d’entier
so it

dendent s deROMANOFF a démontre

à

reest

tel que, pourn

N , le graphe descie, i. e. :3. Le problème de Romanoff (cf. fil’]. p.

2 T~- + p,

N230 ).

(cf. [27] et [23], p. 168-173) que les nombres de la forme

kentier, p premier et plus petits que x, sont en quantité supérieucx . P. ERDÖS a montré [l8] que le nombre de solutions del’équationsupérieur àclog log npour une suite infinie d’entiersn.

Dans le mêmearticle, il démontre l’existence d’une progression arithmétique infinie de nombres
impairs qui ne s’écrivent pas 2~ + p . C’est cette question qui a amené P. ERDOS à
s’intéresser aux systèmes de congruences recouvrants.

Conjecture 1. que

105

est le105

est tel que

105 - 2~est

premier pour tout

k. Montrer

plus grand nombre ayant cette propriété.

Conjecture 2. - Existe-t-il un entierktel que tout nombre s’écrive

LINNIK a démontré

qu’il existe un entier k’ tel que tout entier s’écrive+ 2 ~p + q + 2 1 +avec
i ~ k’ , p et q premiers. SCHINZEL a trouve une
infinité de nombres impairs qui ne s’écrivent pas sous la forme
p+2~+2~,et...

GALLAGHER a montré très récemment que, pour toute >0 , il existe

ktel que ladensité inférieure des nombres

p+2 ~1+...

+2 ~k soit supérieure à 1 -e .

Si-gnalons enfin que la conjecture 1 du paragraphe 4 sur les systèmes de congruences
recouvrant avec des nodules % c entraîne l’existence d’une infinité de nombres
qui ne s’écrivent pas sous la forme q c + 2n ,où q c est un nombre ayant au plus
facteurs premiers.

c

4. Système de congruences recouvrant.

plus complète de la question, et d’autres références,(p. 40 8-4.0~ ) , [10] (p. 235), et aussi A. SCHINZEL [29] qui met en rapport cettequestion avec la réductibilité de certains polynômes.
Pour une étudeDéfinition. - On dit

m 1 m ?_
indicea.

mk , est recouvrant si, pour tout entier...

iqu’un système de congruences(mod mi) , avec
n , il existe

aumoins untel quen -mod m..

a.

Exem p le 1. -0(mod 2) ,0(mod 3),1(mod 4) ,1(mod 6) ,11(mod 12).

Exemple 2. -0(mod 2) ,0(mod 3~ ,1(mod 4) ,7(mod 8),11(mod 12)~et(mod 24) . Pour d’autres exemples,19

donné, existe-t-il un système de congruences recouun système de congruenvrant vérifiant c ~m n 2 ... mk ? CHOI [6] a trouvé
ces recouvrant dont les modules sont tous % 20 .
Conjecture 1. - Pour toutc

Conjecture 2. - Existe-t-il un système recouvrant dont tous les modules soient

impairs ?
Conjecture 3. - On dit qu’un entierm

est recouvrant s’il existe unsystème decongruences recouvrant dont tous les modules sont des diviseurs de m (Ainsi 12
est recouvrant d’après l’exemple 1 ~ . Montrer que, pour tout c > 0 , il existe unentiermLorsquequi ne soit pas recouvrant et qui vérifie

c=2 , on peut voir quem=70> cavecn’est pas recouvrant.

BIBLIOGRAPHIE(A. O. L.) and BIRCH (B. J.) [Editors]. - Computers in number theory.
Proceedings of the Science research council Atlas symposium [2. 1969. Oxford].

[1]

ATKIN

[2]

London, New York, Academic Press, 1971.
BEHREND (F.). - On sequences of integers containing no arithmetic progression,Cas. Mat. Fys., t. 67, 1938, p. 235-238.

[3]

BEHREND-[4](F.). - On sets of integers which contain no three terms in arithmetic

progression, Proc. Nat. Acad. Sc. U. S. A., t. 32, 1946, p. 331-332.
BERLEKAMP (E. R.). - A construction for partitions which avoid long arithmetic
progression, Can. Math. Bull., t. 11, 1968, p. 409-414.

[5]BOMBIERI(E.) and DAVENPORT (H.). - Small differences between prime numbers,[6]Roy. Soc., London, Series A, t. 293, 1966, p. 1-18.
CHOI (S. L. G.). - Covering the set of integers by congruence classes of distinct moduli, Math. of Comp., Washington, t. 25, 1971, p. 885-895.

[7]

CHOWLA (S. D. ) . - There exists an infinity of 3-combinations of primes in
A. P., Proc. Lahore philos. Soc., t. 6, 1944, p. 15-16.

[8]

CHURCHHOUSE (R. F.). - Covering sets and systems of congruences, "Computers
in mathematical research", p. 20-36. - Amsterdam, North-Holland publishing

Proc.

Company, 1968.

(H.). - Multiplicative number theory. - Chicago, Markham publishing
Company, 1967 (Lectures in advanced Mathematics, 1).
[10] ERDÖS (P.). - Some recent advances and current problems in number theory,[9]DAVENPORT"Lectures on modern mathematics". Edited by T. L. Saaty, Vol. 3, p. 196-244.
New York, J. Wiley and Sons, 1965.

-[11] ERDÖS (P. ) . - Some unsolved problems, Publ. Math. Inst. Hung. Acad. Sc., t. 6,1961, p. 221-254.

[12] ERDÖS (P.). - Quelques problèmes de la théorie des nombres. - Genève, L’Enseignement mathématique (Monographies de l’enseignement mathématique, 6,p. 81-135).
[13] ERDÖS (P.). - Problems and results in additive number theory, "Colloque surla théorie des nombres" [1955. Bruxelles], p. 127-137. - Liège, G. Thone ;Paris, Masson, 1956 (Centre belge de Recherches mathématiques).
[14] ERDÖS (P.) and TURAN (P.). - On some sequences of integers, J. London. math.
Soc., t. 11, 1936, p. 261-264.

[15] ERDÖS (P. ) . - Some remarks on number theory, III [en hongrois, avec un résumé
en anglais], Mat. Lapok, t. 13, 1962, p. 28-38. [Pour une traduction, cf.
BENKOVSKI and ERDÖS, Math. of Comp. (à paraître).][16] ERDÖS (P.). - Problems and results on the differences of consecutive primes,Publ. Math., Debrecen, t. 1, 1949, p. 33-37.

[17] ERDÖS (P.) and TURAN (P. ) . - On some sequences )f integers, Bull. Amer. math.
[18]

[19]

[20]

Soc., t. 54, 1948, p. 371-378.
ERDÖS (P.). - On integers of the form 2k + p , Summa Brasil. Math., t. 2,1950, p. 113-123.
KHIN010CIN (A. Ja. ) . - Three pearls of number theory. Translated from the 2nd (1948)
russian edition. - Rochester, Graylock Press, 1952.
MONTGOMERY (H. L. ) . - Topics in multiplicative number theory. - Berlin,Springer-Verlag, 1971 (Lecture Notes in Mathematics, 227).

[21]

NICOLAS (J.-L. ) . - Répartition des nombres premiers, Séminaire Delange-PisotPoitou : Théorie des nombres, 9e année, 1967/68, groupe d’étude n° G6, 4 p.

[22]

PRACHAR (K. ) . - Primzahlverteilung. - Berlin, Springer-Verlag, 1957
lehren der mathematischen Wissenschaften, 91).

[23]
[24]

RADO

(R.). - Studien zur Combinatorik, Math. Z., t. 36, 1933, p. 424-480.
RANKIN (R. A.). - The difference between consecutive prime numbers, J. London
math. Soc., t.

[25]
[26]
[27]

(Grund-13, 1938, p. 242-247.

(R. A.). - The difference between consecutive prime numbers, V, Proc.
Edimburgh math. Soc., t. 13, 1963, p. 29-30.
ROMANOFF (N. P.). - Über einige Satze der additiven Zahlentheorie, Math. Annalen, t. 109, 1934, p. 668-678.

RANKINROTH(K. F.). - On certain sets of integers, J. London math. Soc., t. 28,

1953, p. 104-109.

24-07[28]

SALEM (R.) and SPENCER (D. C.). - On sets of integers which contain no threeterms in an arithmetical progression, Proc. Nat. Acad. Sc. U. S. A., t. 28,
1942, p. 561-563 ; et "Oeuvres mathématiques" de R. SALEM, p. 252-254. -Paris, Hermann, 1967.

[29](A.). - Reducibilit and irreducibility of polynomial and coveringsystems of congruences, Acta Arithm., Warszawa, t. 13, 1967, p. 91-101.

SCHINZEL[30] SCHÖNHAGE (A.). - Eine Bemerkung zur Konstruktion grosser Primzahllucken,
Arch. der Math., Basel, t. 14,

1963, p. 29-30.

(E.). - On sets of integers containing no four elements in arithme-[31]SZEMEREDI[32]

progression, Acta Math. Acad. Sc. Hung., t. 20, 1969, p. 89-104.
VAN DER WAERDEN (B. L.). - Beweis einer Baudet’schen Vermutung, Neiuw Archiefvoor Wiskunde, t. 15, 1928, p. 212-216.
tic

[33]

VAN DER WAERDEN (B. L.). - How the proof of Baudet’s conjecture was found,"Studies in pure mathematics". Papers in combinatorial theory, analysis,presented to Richard Rado, p. 251-260. - London and New York, Academic...

Press, 1971.

(Texte reçu le 15 octobre 1973)
Paul ERDOS

Magyar Tudomanyos Akademia
Matematikai Kutato Intezete

Réaltanoda u 13-15
BUDAPEST V(Hongrie)