sommes de Newton, Fermat

Une propriété sur les sommes de Newton et les fonctions symétriques élémentaires des polynômes de degrés quelconques, unitaires, à coefficients dans Z.
Voir plus loin, au II, un complément dans le cas où ce polynôme est degré trois et n'a pas de terme de degré deux

Dans tout ce qui suit, n et p désigneront des entiers naturels.
Soit P un polynôme de degré n≥1, à coefficients dans Z et unitaire et dont les racines dans C sont x₁, ...,x_n.
On pose, il s'agit des fonctions symétriques élémentaires du polynôme P,
s₁=x₁+ ... +x_n
s₂=x₁x₂+...x₁x_n+x₂x₃+...x₂x_n+...+x_n-1x_n, cad
s₂=∑_i<j  x_ix_j, cela si n≥2
s₃=∑_i<j<k  x_ix_jx_k, cela si n≥3
etc, jusqu'à
s_n=x₁x₂...x_n. On a les relations bien connues : pour i=1, ..., n, s_i=(-1)ⁱ×coefficient de x^n-i dans P, et donc ici, compte-tenu des hypothèses sur P, les s_i sont des entiers, cad dans Z. Enfin, on pose, pour tout entier naturel p, et pour tout i de 1 à n s_i,p= la somme s_i modifiée ainsi : toutes les racines de P qui apparaissent sont élevées à la puissance p : s_1,p=x₁^p+ ... +x_n^p : lorsque p varie, on obtient les sommes dites de Newton, lesquelles seront notées plus loin par S_p
s_2,p=∑_i<j  x_i^px_j^p
s_3,p=∑_i<j<k  x_i^px_j^px_k^p
etc
note : si p=0, et si aucune racine de P est nulle, s_i,p=C_nⁱ, valeur que l'on conviendra de prendre si une des racines de P est nulle.
Les s_i,p appartiennent à l'anneau des polynômes Z[x₁,...,x_n] et sont symétriques (par rapport à leurs n variables x_i) : ils s'écrivent donc (théorème des fonctions symétriques) sous la forme de polynômes à coefficients dans Z des variables s_i ; comme les s_i sont dans Z, les s_i,p sont aussi dans Z.
On a alors le résultat suivant, dû à Schönemann en 1839 :
si p est premier, alors
s_i,p≡s_i (p), cad p divise s_i,p-s_i,
cad p divise s_i,p+(-1)ⁱ×coefficient de x^n-i de P.
Bien entendu, si les x_i sont dans Z, ce résultat s'obtient de façon immédiate par le "petit" théorème de Fermat, puisque celui-ci nous dit que, pour tout p 1er, x_i^p≡x_i (p).
Si n=1 (dans ce cas P=X+a avec a dans Z), alors il y a un seul s_i qui est s₁=x₁ (dans Z) et le résultat ci-dessus est exatement le "petit" théorème de Fermat.
On peut donc considérer que le résultat s_1,p≡s₁ (p), cad x₁^p+ ... +x_n^p ≡ x₁+ ... +x_n (p) est une généralisation du "petit" théorème de Fermat
Cas particulier : on se place dans le cas où le degré de P est 3,
cad P(X)=X³+aX²+pX+q, avec a, p, q dans Z.
En notant ses trois racines, dans C, par x₁, x₂, x₃,
et en posant, pour n entier naturel, S_n=x₁ⁿ+x₂ⁿ+x₃ⁿ, avec S₀=3, le résultat précédent (pour i=1) nous dit que
pour tout n entier naturel premier, S_n est un entier et n divise S_n+a.
Notons qu'ici, il est facile vérifier, sans utiliser le théoréme sur les fonctions symériques, que S_n est toujours (que n soit premier ou pas) un entier relatif, puisque S₀=3, S₁=-a, S₂=(∑x_i)²-2∑x_ix_j=s₁²-2s₂=a²-2p et pour n≥3 S_n+aS_n-1+pS_n-2+qS_n-3=0.
Si n n'est pas premier, il peut diviser S_n+a ( par exemple pour (X-1)³ ), mais ce n'est pas obligé : X³-3X+2 a pour racines 1, 1, -2 et 10 ne divise pas S₁₀=2+(-2)¹⁰ ; on verra un autre exemple à la fin de l'annexe (X³-21X-7, qui lui n'a pas de racine entière).
En fait c'est en essayant de montrer ce résultat (n premier divise S_n+a) dans le cas particulier P(X)=X³+X²-2X-1 (les racines de P ne sont pas entières), cas proposé en exercice par une revue mathématique, que je me suis aperçu que l'on pouvait faire une démonstration générale pour tout polynôme de degré trois (voir cette preuve personnelle en annexe : elle repose sur les formules de Hudde, à savoir que les racines de P sont de la forme u+v, ju+j²v, j²u+jv, ce qui permet d'obtenir des formules explicites pour S_n en fonction de u et v).
Je croyais alors avoir fait, en prouvant cette généralisation à tout polynôme de degré trois ( résultat non citée par la revue), une découverte!
Bien sûr il n'en était rien, puisque cf Schönemann, ce résultat se généralise à tout polynôme et en plus à toute somme fonction symétrique élémentaire des racines!

Preuve du I

Elle repose sur le lemme suivant :

Lemme :
p étant un entier naturel premier,
quelque soit l'entier naturel n non nul, quelques soient les réels u₁, u₂, ...,u_n, on a (u₁+u₂+ ...+u_n)^p=u₁^p+u₂^p+ ...+u_n^p+pH_n(u₁,u₂, ...,u_n), H_n étant un polynôme symétrique de ses n variables et à coefficients dans Z. preuve :

Le résultat est vrai si n=1 : H₁=0
Le résultat est vrai si n=2 : en effet,
(u₁+u₂)^p=u₁^p+u₂ ^p+pH₂(u₁,u₂), avec H₂(u₁,u₂)=∑_k=1^p-1a_ku₁^ku₂^p-k, où a_k=C_p^k/p est un entier naturel, car l'on sait que si p est premier, il divise C_p^k pour k dans {1 ; ... ; p-1}.
Par ailleurs H₂ est un polynôme symétrique par raport à ses n variables car c'est la différence de deux polynômes symétriques (ou parceque a_p-k=a_k).
Supposons maintenant le résultat vrai pour n≥1, et montrons qu'il est vrai pour n+1 :

cf le résultat est vrai pour n=2,
(u₁+u₂+ ...+u_n+u_n+1)^p=(u₁+u₂+ ...+u_n)^p+u_n+1^p+pH₂(u₁+u₂+ ...+u_n,u_n+1),
et d'après l'hypothèse de récurrence,
(u₁+u₂+ ...+u_n+u_n+1)^p=u₁^p+u₂^p+ ...+u_n^p+u_n+1^p+pH_n+1(u₁,u₂, ...,u_n,u_n+1),
avec H_n+1(u₁,u₂, ...,u_n,u_n+1)=H₂(u₁+u₂+ ...+u_n,u_n+1)+H_n(u₁,u₂, ...,u_n).
On voit tout de suite que H_n+1, polynôme en u₁,u₂, ...,u_n,u_n+1 est à coefficients dans Z, car H₂ et H_n sont à coefficients dans Z ; H_n+1 est symétrique, car c'est la différence de deux polynômes symétriques. Donc le résultat est vrai pour n+1, ce qui prouve le lemme.

Remarque 1 : évidemment en remplaçant tous les u_i par 1, on obtient le "petit" théorème de Fermat, puisque H_n(1,1,...,1) est dans Z.

Remarque 2 : une preuve "classique" de ce théorème de Fermat est de partir, u₁, u₂ étant cette fois entiers, de (u₁+u₂)^p=u₁^p+u₂ ^p+pK, avec K dans Z (puisque p premier divise C_p^k pour k non nul et non égal à p), soit (u₁+u₂)^p ≡ u₁^p+u₂^p (p), puis on termine par une récurrence évidente pour arriver à (u₁+u₂+...+u_n)^p ≡ u₁^p+u₂^p+...+u_n^p (p) et là encore on fait u_i=1.

Remarque 3 : dans le cas n=3, on peut donner un résultat plus précis pour le lemme :

p étant un entier naturel premier, pour tous réels x,y,z on a

(x+y+z)^p=x^p+y^p+z^p+p(x+y)(x+z)(y+z)R(x,y,z), avec R polynôme en x,y,z, symétrique, à coefficients dans Z et homogéne de degré p-3.

(perso : voir dossier Fermat ≥3 page 2_0_2).
Ce résultat a été utilisé par Lamé en 1839 (même année que Schönemann), pour démontrer le grand théorème de Fermat dans le cas de l'exposant 7 ( il n'existe pas a,b,c entiers relatifs, tous non nuls, tels que a⁷+b⁷=c⁷).
Dans ce cas R(x,y,z)=(x²+y²+z+²xy+xz+yz)²+xyz(x+y+z) ; ce qui donne pour x=y=z=1, 3⁷=3+7×8×(6²+3).

Application du lemme pour obtenir le résultat annoncé
Ne pouvant faire des indices imbriqués en html, je serai amené remplacer k_i par k_i.
s_i=∑_{k_1<k_2...<k_i} x_{k_1}x_{k_2}...x_{k_i}=∑_j=1^N e_j, avec N=C_nⁱ et les e_j étant les produits de i racines de P.
Remarque : si i=1, N=n et les e_j sont les x_j.
s_i,p=∑_{k_1<k_2...<k_i} x_{k_1}^px_{k_2}^p...x_{k_i}^p.
Rappelons que l'on sait que s_i et s_i,p sont dans Z (voir énoncé).
Cf le lemme (on remplace les u_i par les e_i), (s_i)^p=s_i,p+pH(e₁,...,e_N), avec H polynôme de ses N variables e_j, à coefficients dans Z, et symétrique.
Donc H(e₁,...,e_N)=Q(x₁,...,x_n), avec Q polynôme des n variables x_i à coefficients dans Z, vu que chaque e_i est lui même un polynôme en x_i, réduit à un seul monôme de coefficient 1.
En outre Q étant la différence de deux polynômes symétriques ( ((s_i)^p-s_i,p)/p ), c'est un polynôme symétrique et on peut alors encore appliquer le théorème sur les fonctions symétriques : Q s'écrit sous forme d'un polynôme des variables s_i à coefficients dans Z ; comme les s_i sont dans Z, Q(x₁,...,x_n) est dans Z, donc (s_i)^p-s_i est égal à p multiplié par un élément de Z.
On peut alors dire que (s_i)^p ≡s_i,p (p), soit cf Fermat, s_i ≡s_i,p (p).

II
Un complément pour les polynômes de degré trois sans terme de second degré.
Résultat "personnel".
n étant un entier naturel et S_n étant la somme des puissances nièmes des trois racines du polynôme X³+pX+q, avec p, q dans Z (S₀=3), alors cf le I (voir le cas particulier de l'énoncé), S_n est dans Z, et pour tout n 1er, n divise S_n.
Mais on peut faire beaucoup mieux question divisibilité :
si n est 1er, ≥5, alors

S_n est un polynôme en p et q dont tous les coefficients sont entiers et divisibles par n
npq ou np²q divise l'entier S_n

Attention : pour le 1) et 2) ci-dessous, il n'est pas nécessaire que p et q soient dans Z (p et q réels suffit) ; seul le 3) exige que p et q soient dans Z.
1) pour tout n dans N-{0 ; 1}, S_n est un polynôme en p et q, à coefficients entiers ( S₀=3 et S₁=0 sont aussi des polynômes en p et q, mais ces cas sont "trop" particuliers pour les formules ci-dessous : notamment le polynôme nul n'a pas de degré)
il est de degré E(n/2), cad n/2 si n est pair, (n-1)/2 si n est impair

sa valuation (voir note ci-dessous) est v_n (que je noterai parfois, pour des commodités html, v_n)
si n≡0 (3), v_n=E(n/3)=n/3
si n≡1 (3), v_n=E(n/3)+1=(n+2)/3
si n≡2 (3), v_n=E(n/3)+1=(n+1)/3
note : la valuation d'un polynôme est le plus petit degré des termes non nuls : X⁴+25X² est de valuation 2 ; S₁₆=2p⁸-48p⁵q²+40p²q⁴ est de valuation 6.

S_n=∑_{k=v_n}^E(n/2) c_n,kp^3k-nq^n-2k, les c_n,k étant entiers

∑_{k=v_n}^E(n/2)c_n,k(-3)^3k-n2^n-2k=2+(-2)ⁿ : c'est la valeur de S_n lorsque p=-3, q=2. .
note 1 : rappelons (voir énoncé du I) que si n est 1er et si les racines de X³+pX+q sont entières ( donc p et q sont dans Z ; c'est le cas de X³-3X+2), Fermat prouve tout de suite que n divise S_n ; par exemple ici 2+(-2)ⁿ≡2-2=0 (n).
note 2 : pour n=0 et 1 qui ont été exclus au départ, on peut remarquer que S₀ est toujours (peu importe les valeurs de p et q) égal à 2+(-2)⁰ et S₁ toujours égal à 2+(-2)¹.
pour k dans [v_n ; E(n/2)], c_n,k=-c_n-2,k-1-c_n-3,k-1, les c_i,j du membre de droite étant nuls si j n'est pas dans [v_i ; E(i/2)]
Par exemple, c_16,7=-c_14,6-c_13,6, soit, cf tableau ci-après -48=-(35)-(13).

terme de plus haut degré de S_n ( correspond à k=E(n/2)) :
si n est pair, le terme de plus haut degré est 2(-1)^n/2p^n/2,
si n est impair, le terme de plus haut degré est n(-1)^(n-1)/2p^(n-3)/2q,
note :
si n est pair, n divise le coefficient du terme de plus haut degré uniquement si n=2, cad si n est premier
si n est impair, n divise le coefficient du terme de plus haut degré

terme de plus bas degré de S_n (correspond à k=v_n) :

si n≡0 (3), le terme de plus bas degré est 3(-1)^n/3q^n/3,
si n≡1 (3), le terme de plus bas degré est (n(n-1)/6)(-1)^(n+2)/3p²q^(n-4)/3
si n≡2 (3), le terme de plus bas degré est n(-1)^(n+1)/3pq^(n-2)/3
note 1 :
ces résultats restent valablent même si n=0 ou 1.
note 2 :
le signe du coefficient c_{n,v_n} du terme de plus bas degré est toujours celui de (-1)^v_n
note 3 :
si n est un multiple de 3, n divise le coefficient du terme de plus bas degré uniquement si n=3, cad si n est premier
si si n≡2 (3), n divise le coefficient du terme de plus bas degré
attention : si n≡1 (3), n ne divise pas forcément le coefficient du terme de plus bas degré : pour cela, il faut et il suffit que 6 divise n-1 (ce qui n'est pas obligé même si n≡1 (3) : n=16).
Par contre, si n≡1 (3) et si n est premier, alors n divise le coefficient du terme de plus bas degré : en effet dans ce cas n=3p+1, avec p obligatoirement pair (sinon n est pair, donc pas premier, puisque il ne peut être égal à 2) et donc (n-1)/6=p/2 est entier.
Enfin, parmi les n tels que n≡1 (3), qui ne sont pas premiers, les plus petits qui divisent le coefficient du terme de plus bas degré sont 25 et 49 (on examine les nombres de la forme 1+6p qui ne sont pas premiers).

deux cas particuliers :
si q=0 soit n est pair et S_n=2(-1)^n/2p^n/2, soit n est impair et S_n=0
si p=0 soit n≡0 (3) et S_n=3(-1)^n/3q^n/3, soit n≡1 ou 2 (3) et S_n=0
Note : pour la preuve de ces deux cas particuliers p=0, q=0, voir début de l'annexe.

2) n étant un nombre premier supérieur ou égal à 5
si n≡1 (3) alors le polynôme (en p et q) S_n est factorisable par p²q, et tous ses coefficients sont divisibles par n
si n≡2 (3) alors le polynôme (en p et q) S_n est factorisable par pq, et tous ses coefficients sont divisibles par n
Note : le fait que tous les coefficients de S_n (polynôme en p et q) soient divisibles par n, lorsque n est 1er, reste vrai pour n=2 et n=3.

3) n étant un nombre premier supérieur ou égal à 5 et p et q étant cette fois dans Z (donc cf le I, S_n est dans Z)
si n≡1 (3) alors np²q divise l'entier S_n
si n≡2 (3) alors npq divise l'entier S_n
Note : c'est une conséquence immédiate du 2).

Avant de commencer la preuve, on peut vérifier ces résultats pour n≤21 : voir sur page suivante le tableau de ces S_n, calculs faits à partir de S₀=3, S₁=0, S₂=(∑x_i)²-2∑x_ix_j=S₁²-2p=-2p, et pour n≥3, S_n=-pS_n-2-qS_n-3.

Remarque : on verra dans l'annexe 2 une formule explicite de S_n, du moins pour n premier, avec application à S₁₁, S₁₃, S₁₇ ; il y a en fait deux formules selon que n≡1 (3) ou n≡2 (3).

n	S_n
0	3
1	0
2	-2p
3	-3q
4	2p²
5	5pq
6	-2p³+3q²
7	-7p²q
8	2p⁴-8pq²
9	9p³q-3q³
10	-2p⁵+15p²q²
11	-11pq(p³-q²)
12	2p⁶-24p³q²+3q⁴
13	13p²q(p³-2q²)
14	-2p⁷+35p⁴q²-14pq⁴
15	-15p⁶q+50p³q³-3q⁵
16	2p⁸-48p⁵q²+40p²q⁴
17	17pq(p⁶-5p³q²+q⁴)
18	-2p⁹+63p⁶q²-90p³q⁴+3q⁶
19	19p²q(-p⁶+7p³q²-3q⁴)
20	2p¹⁰-80p⁷q²+175p⁴q⁴-20pq⁶
21	21p⁹q-196p⁶q³+147p³q⁵-3q⁷

Note : le lecteur "ayant des doutes" peut vérifier, voir 1) ci-dessus, que dans le cas p=-3, q=2 on a effectivement, pour n=0, 1, 2, 3, ..., 21, S_n=2+(-2)ⁿ .

Preuves du II

preuve du 1)
Le fait que S_n soit un polynôme en p et q à coefficients entiers est immédiat : c'est vrai pour S₀=3, S₁=0, S₂=(∑x_i)²-2∑x_ix_j=S₁²-2p=-2p, et une récurrence facile à partir de la relation S_n=-pS_n-2-qS_n-3 permet de conclure tout de suite.

Précisons ce polynôme, qui à priori s'écrit ∑c_s,tp^sq^t, les c_s,t étant les coefficients, dont on sait qu'ils sont entiers ; par contre on ne connaît pas encore le domaine (fini) de sommation.
Si on prend p=-3x² et q=2x³, avec x réel quelconque non nul, alors 4p³+27q²=0, donc les racines de X³+pX+q sont 3q/p=-2x et -3q/(2p)=x (double), donc S_n=xⁿ+xⁿ+(-2x)ⁿ=xⁿ(2+(-2)ⁿ), et ainsi pour tout x réel non nul on a
xⁿ(2+(-2)ⁿ)=∑c_s,t(-3)^s2^tx^2s+3t : donc pour tout couple (s,t) tel que c_s,t est un coefficient non nul du polynôme S_n, on doit avoir 2s+3t=n (un polynôme non nul a un nombre fini de racines), et donc ∑c_s,t(-3)^s2^t=2+(-2)ⁿ.
Cette équation diophantienne 2s+3t=n est facile à résoudre dans Z×Z :

le couple (-n,n) est une solution particulière et par différence membre à membre on obtient 2(s+n)=3(n-t), donc 2 divise n-t, soit t=n-2k, et donc s=3k-n ; réciproquement tous ces couples sont solutions. Donc les couples (s,t) sont tous de la forme s=3k-n, t=n-2k, k dans Z, mais ici s et t doivent être positifs ou nuls, ce qui donne n/3≤k≤n/2, donc v_n≤k≤E(n/2), avec v_n=n/3, si 3 divise n et v_n=E(n/3)+1 sinon.
Donc on a prouvé que S_n=∑_{k=v_n}^E(n/2) c_n,kp^3k-nq^n-2k, les c_n,k étant entiers.

La relation S_n=-pS_n-2-qS_n-3 permet alors de dire que pour tout k dans [v_n ; E(n/2)],
c_n,k=-c_n-2,k-1-c_n-3,k-1, les c_i,j du membre de droite étant nuls si j n'est pas dans [v_i ; E(i/2)].
Voir à la fin de la preuve du 1) la remarque 2 sur cette relation.

Mais pour l'instant, on n'a pas encore prouvé que c_n,k pour k=E(n/2) et c_n,k pour k=v_n sont non nuls, cad on n'a pas encore prouvé que S_n est de degré E(n/2) et de valuation v_n.
Pour cela on va faire deux récurrences.

Récurrence sur le terme de plus haut degré :

on fait l'hypothèse de récurrence H_n suivante pour n≥1 :

S_2n est de degré n, le (seul) terme de de degré n étant 2(-1)ⁿpⁿ
S_2n+1 est de degré n, le (seul) terme de de degré n étant (2n+1)(-1)ⁿp^n-1q

On vérifie sans peine que H₁ et H₂ sont vraies (voir tableau des premiers S_n)
On suppose maintenant que H₁, H₂,..., H_n sont vraies (n≥2) et on va montrer que H_n+1 est vraie :

S_2n+2=-pS_2n-qS_2n-1
-pS_2n est de degré 1+n=n+1 alors que -qS_2n-1 est de degré 1+n-1=n, donc S_2n+2 est de degré n+1, le terme de degré n+1 étant -p×2(-1)ⁿpⁿ=2(-1)ⁿ⁺¹pⁿ⁺¹ : la 1ière partie de H_n+1 est donc vraie
S_2n+3=-pS_2n+1-qS_2n
-pS_2n+1 est de degré 1+n=n+1 et -qS_2n est aussi de degré 1+n=n+1 ; il faut examiner la somme des deux termes de degré n+1 :
c'est -p×(2n+1)(-1)ⁿp^n-1q-q×2(-1)ⁿpⁿ=(2n+3)(-1)ⁿ⁺¹pⁿq : la 2ième partie de H_n+1 est donc vraie

Donc, H_n+1 est vraie, et ainsi par réurrence on a montré que H_n est vraie pour tout n≥1, ce qui prouve le résultat de l'énoncé.

Récurrence sur le terme de plus bas degré

on fait l'hypothèse de récurrence H_n suivante pour n≥1 :

S_3n est de valuation v_3n=n, le terme de plus bas degré étant 3(-1)ⁿqⁿ
S_3n+1 est de valuation v_3n+1=n+1, le terme de plus bas degré étant e₁p²q^n-1, avec e₁=(n(3n+1)/2)(-1)ⁿ⁺¹
S_3n+2 est de valuation v_3n+2=n+1, le terme de plus bas degré étant e₂pqⁿ, avec e₂=(3n+2)(-1)ⁿ⁺¹

On vérifie sans peine que H₁ est vraie (voir tableau des premiers S_n)
On suppose maintenant que H₁, H₂,..., H_n sont vraies (n≥1) et on va montrer que H_n+1 est vraie :

S_3n+3=-pS_3n+1-qS_3n
donc le terme de plus bas degré vient que de -qS_3n : c'est -q×3(-1)ⁿqⁿ=3(-1)ⁿ⁺¹qⁿ⁺¹ et la 1ière partie de H_n+1 est vraie
S_3n+4=-pS_3n+2-qS_3n+1
donc le terme de plus bas degré de S_3n+4 est -e₂p²qⁿ-e₁p²qⁿ=-(e₁+e₂)p²qⁿ=(-1)ⁿ⁺²(3n+2+n(3n+1)/2)p²qⁿ=(-1)ⁿ⁺²((n+1)(3n+4)/2)p²qⁿ (qui est bien non nul) : la 2ième partie de H_n+1 est vraie
S_3n+5=-pS_3n+3-qS_3n+2
donc le terme de plus bas degré de S_3n+5 est -p×3(-1)ⁿ⁺¹qⁿ⁺¹ (cf preuve de la 1ière partie de H_n+1)-e₂pqⁿ⁺¹=(3(-1)ⁿ⁺²-e₂)pqⁿ⁺¹=(-1)ⁿ⁺²(3+(3n+2))pqⁿ⁺¹=(-1)ⁿ⁺²(3n+5)pqⁿ⁺¹ (qui est bien non nul) : la 3ième partie de H_n+1 est vraie

Donc, H_n+1 est vraie, et ainsi par récurrence on a montré que H_n est vraie pour tout n≥1.
Pour obtenir les résultats annoncés il ne reste plus qu'à faire le passage (3n, 3n+1, 3n+2), pour n≥1, à (n≡0 (3), n≡1 (3), n≡2 (3) ), et de les vérifier directement pour S₀, S₁, S₂. Remarque 1 :
le lecteur peut se demander d'où viennent ces formules pour le coefficient du terme de plus bas degré, surtout pour S_3n+1 (celles pour le coefficient du terme de plus haut degré se devinent tout de suite à la lecture des premiers S_n)!
En fait en notant le coefficient c_{n,v_n} du terme de plus bas degré de S_n par k_n, du raisonnement par récurrence ci-dessus on peut tirer :

k_3n=-k_3n-3
k_3n+1=-k_3n-2-k_3n-1
k_3n+2=k_3n-3-k_3n-1

Et donc en prenant comme matrice colonne K_n=^t(k_3n k_3n+1 k_3n+2), on a K_n=AK_n-1, avec A la matrice 3×3 suivante

-1	0	0
0	-1	-1
1	0	-1

Donc pour tout n dans N, K_n=AⁿK₀.
Et on vérifie facilement que (-1)ⁿAⁿ est la matrice ci-dessous

1	0	0
-n(n-1)/2	1	n
-n	0	1

(soit on calcule les premières puissances de A, on devine la formule et on termine par une récurrence immédiate, soit on écrit que A=B-I, avec B=(b_i,j) matrice dont tous les éléments sont nuls sauf b_3,1=1 et b_2,3=-1 : alors B² a tous ses éléments nuls sauf celui en (2,1) qui vaut -1, B³=0, et pour n≥2, Aⁿ=(-I)ⁿ+nB(-I)^n-1+(n(n-1)/2)B²(-I)^n-2, soit (-1)ⁿAⁿ=I-nB+(n(n-1)/2)B², encore vrai pour n=1).
Comme ^tK₀=(3 0 -2), on obtient

k_3n=3(-1)ⁿ
k_3n+1=(-1)^n-1(3n(n-1)/2+2n)
k_3n+2=(-1)^n-1(3n+2)

Ce qui correspond aux résultats ci-dessus.

Remarque 2 : la relation, pour tout k dans [v_n ; E(n/2)], c_n,k=-c_n-2,k-1-c_n-3,k-1, les c_i,j du membre de droite étant nuls si j n'est pas dans [v_i ; E(i/2)] n'est pas facile à exploiter.
Essayons de voir ce que cela donne pour le coefficient du terme de plus bas degré.

c_{3n,v_(3n)}=-c_{3n-2,v_(3n)-1}-c_{3n-3,v_(3n)-1}.
v_3n=v_(3n)=3n/3=n, et donc v_(3n)-1=n-1.
v_3n-2=(3n-2+2)/3=n : donc on n'a pas v_(3n)-1 supérieur ou égal à v_3n-2 et donc c_{3n-2,v_(3n)-1}=0
v_3n-3=(3n-3)/3=n-1 et donc v_(3n)-1=v_3n-3, ce qui veut dire que
c_{3n,v_(3n)}=-c_{3n-3,v_(3n-3)}, et en posant k_n=c_{n,v_(n)}, on retrouve la relation vue ci-dessus k_3n=-k_3n-3.

Essayons de voir ce que donne c_{3n+1,v_(3n+1)}=-c_{3n-1,v_(3n+1)-1}-c_{3n-2,v_(3n+1)-1}.
v_(3n+1)=v_3n+1=(3n+3)/3=n+1, et donc v_(3n+1)-1=n.
v_(3n-1)=(3n-1+1)/3=n, donc c_{3n-1,v_(3n+1)-1}=-c_{3n-1,v_(3n-1)}
v_(3n-2)=(3n-2+2)/3=n, donc c_{3n-2,v_(3n+1)-1}=-c_{3n-2,v_(3n-2)}
et on retrouve la relation k_3n+1=-k_3n-1-k_3n-2

Terminons par l'exploitation de c_{3n+2,v_(3n+2)}=-c_{3n,v_(3n+2)-1}-c_{3n-1,v_(3n+2)-1}.
v_(3n+2)=v_3n+2=(3n+3)/3=n+1 et v_(3n+2)-1=n.
v_(3n)=3n/3=n et donc c_{3n,v_(3n+2)-1}=c_{3n,v_(3n)}
v_(3n-1)=(3n-1+1)/3=n et donc c_{3n-1,v_(3n+2)-1}=c_{3n-1,v_(3n-1)}
et on obtient la relation k_3n+2=-k_3n-k_3n-1, et comme on a vu ici que k_3n=-k_3n-3, on retrouve k_3n+2=k_3n-3-k_3n-1

preuve du 2) Utilisons la formule S_n=∑_{k=v_n}^E(n/2)c_n,kp^3k-nq^n-2k, les c_n,k étant entiers.
n étant 1er supérieur ou égal à 5, il ne peut être divisible ni par 2, ni par 3, donc les exposants 3k-n et n-2k ne sont jamais nuls, donc toujours supérieurs ou égaux à 1, et le polynôme S_n, en p et q, est factorisable par pq.
n restant 1er supérieur ou égal à 5, envisageons les deux possibilités

soit n≡1 (3) : alors 3k-n ne peut prendre la valeur 1, puisque 3k-n=1 donne n≡-1 (3), soit n≡2 (3), ce qui est contraire à l'hypothèse, et donc cette fois S_n est factorisable par p²q
soit n≡2 (3) : donc n=2+3K, n=-1+3(K+1), et en prenant k=K+1=(n+1)/3, on obtient dans S_n un terme en pq^(n-2)/3 (cette valeur de k est licite car v_n≤(n+1)/3≤E(n/2)) et donc cette fois S_n n'est pas factorisable par p²q

Note : ces factorisations par pq ou p²q sont bien sûr cohérentes avec les derniers résultats du 1, qui disent que si n≡1 ou 2 (3) et p=0, S_n est le polynôme (en q) nul ou que si n impair et q=0, S_n est le polynôme (en p) nul ; ces résultats auraient d'ailleurs pû être utilisés pour factoriser S_n par pq lorsque n est 1er, supérieur ou égal à 5 (donc ≡1 ou 2 (3) et impair).

Reste à prouver la divisibilité par n, lorsqu'il est premier (sans être obligatoirement supérieur ou égal à 5) , de tous les coefficients c_n,k de S_n (pour n impair c'est déjà acquis pour le coefficient du terme de plus haut degré puisque celui-ci est égal à n(-1)^(n-1)/2).
Pour cela, on va utiliser le
Lemme :

Soient k(≥1) entiers a₁, ..., a_k avec a₁ et a_k non nuls et r (>k) un entier naturel premier
On suppose qu'il existe s entier naturel tel que pour tout entier x, r divise a₁x^s+a₂x^s+1+...+a_kx^s+k-1.
Alors, tous les a_i sont divisibles par r. preuve :
si k=1, c'est trivial (on prend x=1) ; on se place donc maintenant dans le cas k≥2.
Pour i=1, 2, ..., k posons x_i=i : r divise donc (pour tout i dans {1 ; 2 ; ... ; k})
a₁(x_i)^s+a₂(x_i)^s+1+...+a_k(x_i)^s+k-1=(x_i)^s(a₁+a₂(x_i)¹+...+a_k(x_i)^k-1),
mais comme r est 1er il doit diviser l'un des facteurs, mais il ne peut diviser x_i=i puisque 1≤i≤k<r, donc
r divise a₁+a₂(x_i)¹+...+a_k(x_i)^k-1.
Cad a₁+a₂(x_i)¹+...+a_k(x_i)^k-1≡0 (r) pour i=1, 2, ..., k ;
donc, modulo r, a₁, a₂, ...., a_k sont solutions d'un systéme linéaire homogéne de k inconnues à k équations dont le déterminant D a pour ième ligne
1 x_i (x_i)² ... (x_i)^k-1
D est donc un déterminant de Vandermonde et ainsi D=π_1≤i<j≤k(x_j-x_i) ; or r ne divise aucun des x_j-x_i, puisque pour i≠j, |x_j-x_i| est dans {1 ; 2; ... ; k-1} lequel est inclu dans {1 ; 2 ; ... ; r-2} et ainsi, modulo r, D est non nul et on a un systéme homogéne de Kramer, cela dans le corps Z/rZ : toutes les inconnues sont donc nulles, cad modulo r tous les a_i sont nuls, ce qui veut dire que tous les a_i sont divisibles par r. Appliquons ce lemme.
Pour p=q=x, S_n=∑_{j=v_n}^E(n/2)c_n,jx^j.
Ici, par rapport aux notations du lemme, k=E(n/2)-v_n+1, a_j=c_{n,v_n+j-1},a₁=c_{n,v_n} et a_k=c_n,E(n/2) sont bien non nuls (puisque S_n est de valuation v_n et de degré E(n/2)), et r=n (nombre 1er quelconque) et s=v_n.
Avant d'appliquer le lemme il y a lieu cependant de vérifier que l'on a effectivement r>k, cad n>k : on a évidemment k≤n/2-v_n+1, et comme v_n=n/3 ou(n+2)/3 ou (n+1)/3, pour n≥3, v_n≥1 et ainsi k≤n/2<n ; mais si n=2, v_n=(2+1)/3=1 et k=1-1+1=1<2=n.
Finalement on a toujours n>k.
Cf le I (voir le cas particulier X³+aX²+pX+q avec a=0 cité dans l'énoncé de ce I), si n est 1er, alors pour tout p et q entiers, n divise S_n, donc en particulier lorsque p=q=x est entier quelconque, n divise S_n=∑_{j=v_n}^E(n/2)c_n,jx^j et le lemme donne que tous les c_n,j sont divisibles par n.

Annexe

On considère ici le cas particulier mis en évidence dans le I :

si P est le polynôme X³+aX²+pX+q, avec a, p, q dans Z
si x₁, x₂, x₃ sont les racines de P dans C
si pour n entier naturel, S_n=x₁ⁿ+x₂ⁿ+x₃ⁿ, avec S₀=3,

alors pour tout n entier naturel premier, S_n est un entier et n divise S_n+a. Il s'agit ici de donner une autre preuve de ce résultat particulier (cad sans utiliser le résultat de Schönemann ).
Cette preuve est plus compliquée, mais c'est celle que j'avais trouvée, seul dans mon coin...., et elle m'a conduit au II.
Elle repose sur la mise en évidence d'une formule explicite de S_n en fonction de p et q, du moins pour n premier et a=0.

preuve de l'annexe

Redisons qu'ici, il est évident que S_n est toujours un entier relatif, puisque S₀=3, S₁=-a, S₂=(∑x_i)²-2∑x_ix_j=a²-2p et pour n≥3, S_n+aS_n-1+pS_n-2+qS_n-3=0.

Pour la divisibilité de S_n+a par n, on va d'abord traiter le cas a=0, puis s'y ramener.

Cas a=0 : il s'agit alors de montrer que si n est entier naturel 1er alors il divise S_n
C'est évident dans les trois cas particuliers suivants :

si p=q=0
dans ce cas les trois racines sont 0 et S_n est toujours nul (pour tout n≥1), donc divisible par n, pour tout n≥1 en fait
si p=0 et q non nul
les racines de X³+q sont les trois racines 3ièmes de -q, soient r, rj, rj² , avec r une racine 3ième de -q, et donc S_n=rⁿ(1+jⁿ+j²ⁿ), d'où
- si n≡1 ou 2 (3), 1+jⁿ+j²ⁿ=1+j+j²=0 et S_n=0,
- si n≡0 (3), 1+jⁿ+j²ⁿ=1+1+1=3 et S_n=3rⁿ=3(-q)^n/3.
donc, si n est 1er soit c'est 3 et S₃=-3q, divisible par 3, sinon n≡1 ou 2 (3) et S_n=0, divisible par n
si q=0 et p non nul
les racines de X³+pX sont 0 et les deux racines 2ièmes de -p, donc S_2n=2(-p)ⁿ, S_2n+1=0,
d'où si n est 1er soit c'est 2 et S₂=-2p, divisible par 2, sinon n est impair et S_n=0, divisible par n.
note : si on fait q=0 dans le 2ième cas ou p=0 dans le 3ième cas on retrouve le 1er cas p=q=0.

Traitons maintenant le cas général où p et q sont quelconques (entiers).
Pour expliciter les trois racines de X³+pX+q, on pose (méthode de Hudde) X=u+v avec uv=-p/3, et on voit tout de suite que u³ et v³ sont les racines Z₁ et Z₂ de Z²+qZ-p³/27 :
les trois racines de X³+pX+q sont donc u+v, ju+j²v, j²u+jv, avec u une racine 3ième de Z₁, v une racine 3ième de Z₂ et uv=-p/3.
On peut alors écrire S_n=(u+v)ⁿ+(ju+j²v)ⁿ+(j²u+jv)ⁿ.
Lemme :

soit A l'anneau {e/3^k ; e dans Z ; k dans N} et R(X₁,X₂), un polynôme à coefficients dans A, symétrique en X₁ et X₂ : alors R(u³,v³) est dans A. preuve : (voir par exemple Théorie de nombres, lemme 9.2, de Daniel Duverney, chez Dunod), R(X₁,X₂) s'écrit sous forme d'un polynôme des deux variables s₁=X₁+X₂ et s₂=X₁X₂, à coefficients dans A, et comme u³+v³=-q est dans A et u³v³=-p³/27 est dans A, on a bien R(u³,v³) dans A. Montrons maintenant que tout n 1er divise S_n.
Si n=2, S₂=6uv=-2p, divisible par 2.
Si n=3, S₃=3(u³+v³)=-3q divisible par 3.
On suppose mantenant n≥5.
S_n=∑ⁿ_k=0C_n^k t_ku^kv^n-k, avec t_k=1+j^k(j²)^n-k+(j²)^kj^n-k=1+j^2n-k+j^n+k=1+(j^n+k)²+j^n+k.
n étant 1er≥5, soit n≡1 (3), soit n≡2 (3).

si n≡1 (3), c'est-à-dire n=3r+1, avec r entier naturel pair (puisque n est 1er distinct de 2, n est impair) ; ainsi t_k=1+(j^k+1)²+j^k+1 pour k=3k', t_k=1+j²+j=0
pour k=3k'+1, t_k=1+j+j²=0
pour k=3k'+2, t_k=1+1+1=3 Donc S_n=3∑_k'=0^r-1C_n^3k'+2 u^3k'+2v^n-(3k'+2) ("les" 3k'+2 décrivent {2;5;...;n-2}).
Mais C_n^3k'+2=C_n^n-3k'-2=C_n^3(r-1-k')+2, et si k' décrit {0 ; ... ; r/2-1} (rappel : r est pair) alors r-1-k' décrit {r-1-r/2+1 ; ... ; r-1}={r/2 ; ... ; r-1}, donc
S_n=3∑_k'=0^r/2-1C_n^3k'+2 (u^3k'+2v^n-(3k'+2)+u^3(r-1-k')+2v^{n-(3(r-1-k')+2)})
S_n=3∑_k'=0^r/2-1C_n^3k'+2 (u^3k'+2v^3(r-1-k')+2+u^3(r-1-k')+2v^3k'+2)
S_n=3(-p/3)²∑_k'=0^r/2-1C_n^3k'+2 (u^3k'v^3(r-1-k')+u^3(r-1-k')v^3k'), puisque u²v²=(-p/3)².
On constate alors que dans ce dernier ∑ les coefficients des C_n^3k'+2 sont des polynômes symétriques en u³ et v³, à coefficients entiers, donc dans A, et cf le lemme ci-dessus, les coefficients des C_n^3k'+2 sont dans l'anneau A.
Par ailleurs n divise C_n^3k'+2 (puisque n est 1er et que 3k'+2 est dans {1;2;...;n-1}), et p²/3 est dans A.
Finalement, on peut écrire S_n=n×e/3^s, avec e dans Z, s dans N ; ainsi n×e=3^sS_n.
Comme S_n est un nombre entier, cette égalité prouve que n divise 3^sS_n et n étant un nombre premier supérieur ou égal à 5, n est 1er avec 3^s, et donc n divise S_n.

si n≡2 (3), c'est-à-dire n=3r+2, avec r entier naturel impair (puisque n est 1er distinct de 2, n est impair) ; ainsi t_k=1+(j^2+k)²+j^2+k.

pour k=3k', t_k=1+j+j²=0
pour k=3k'+1, t_k=1+1+1=3
pour k=3k'+2, t_k=1+j²+j=0 Donc S_n=3∑_k'=0^rC_n^3k'+1 u^3k'+1v^n-(3k'+1) ("les" 3k'+1 décrivent {1;4;...;n-1}).
Mais C_n^3k'+1=C_n^n-(3k'+1)=C_n^3(r-k')+1, et si k' décrit {0 ; ... ; (r-1)/2} (rappel : r est impair) alors r-k' décrit {(r+1)/2 ; ... ; r}, et comme (r-1)/2+1=(r+1)/2, on a
S_n=3∑_k'=0^(r-1)/2C_n^3k'+1 (u^3k'+1v^3(r-k')+1+u^3(r-k')+1v^3k'+1)
S_n=3(-p/3)∑_k'=0^(r-1)/2C_n^3k'+1 (u^3k'v^3(r-k')+u^3(r-k')v^3k').
Un raisonnement identique en tout point au précédent permet alors de conclure aussi à n divise S_n.

Cas où a est quelconque
En posant X=(Y-a)/3, X³+aX²+pX+q=0<=>Y³+p'Y+q'=0, avec p'=-3a²+9p, q'=2a³-9ap+27q, lesquels sont donc dans Z. En notant y_i les racines de Y³+pY+q, le cas précédent prouve que pour tout entier naturel n, S'_n=y₁ⁿ+y₂ⁿ+y₃ⁿ (S'₀=3) est un entier relatif, qui est divisible par n, si en outre n est 1er.
Or S_n=((y₁-a)/3)ⁿ+((y₂-a)/3)ⁿ+((y₃-a)/3)ⁿ, soit
3ⁿS_n=∑_k=0ⁿ(-1)^kC_n^ka^kS'_n-k (attention, les S'_n-k dépendent de p' et q', donc de a).
Compte-tenu que tout entier naturel n 1er divise C_n^k pour k=1,2,...,n-1, on obtient que 3ⁿS_n≡S'_n+3(-1)ⁿaⁿ (n), et cf ce qui précéde et Fermat, on en déduit que
pour tout entier naturel n 1er, 3S_n≡3(-1)ⁿa (n).
Terminons la démonstration :

si n est 1er et ≥5, alors n est impair, donc 3(S_n+a)≡0 (n), et comme n est 1er avec 3, c'est que n divise S_n+a
si n=2, on a vu que S₂=a²-2p, donc S₂+a=a(a+1)-2p, somme de nombres pairs et on a bien 2 divise S₂+a (3S₂≡3a (2) permet aussi de conclure car 2 étant premier avec 3, 2 divise S₂-a, donc divise S₂+a=S₂-a+2a)
si n=3, S₃=-aS₂-pS₁-3q=-a(a²-2p)-p(-a)-3q et S₃+a=-(a-1)a(a+1)+3pa-3q, somme de multiples de trois et on a bien 3 divise S₃+a

Illustration dans le cas a=0, p=-21, q=-7 .
Vérifions que pour tout entier naturel n≤11 et premier, n divise S_n=x₁ⁿ+x₂ⁿ+x₃ⁿ, les x_i étant les racines de X³-21X-7 (aucune racine n'est entière).
Par utilisation de la relation de récurrence S_n=21S_n-2+7S_n-3 pour n≥3 avec S₀=3, S₁=0, S₂=-2p=42, on obtient

S₃=21, divisible par 3
S₄=882 pas divisible par 4
S₅=735, divisible par 5
S₆=18669, pas divisible par 6
S₇=21609, divisible par 7. etc... : je laisse le lecteur calculer S₈, S₉, S₁₀, et enfin S₁₁

En fait, les formules données au cours de la démonstration ci-dessus (cas a=0), permettent de calculer S_n, sans être obligé de calculer tous les précédents (du moins pour n premier) : cela permettra d'ailleurs au lecteur de vérifier ces formules!
Par exemple S₁₁ : ici n=11=3r+2 avec r=3 et donc (rappelons que uv=-p/3 et u³+v³=-q)
S₁₁=3(-p/3)∑_k'=0¹C₁₁^3k'+1 (u^3k'v^3(3-k')+u^3(3-k')v^3k')
S₁₁=3(-p/3)(C₁₁¹(v⁹+u⁹)+ C₁₁⁴(u³v⁶+u⁶v³))
S₁₁=-p(11(v³+u³)³-3(uv)³(u³+v³)+330u³v³(u³+v³))
S₁₁=-p(11(-q³+3×(p³/27)×(-q))+330(-p³/27)(-q))
S₁₁=-p(-11q³+11p³q)=11pq(q²-p³), qui est bien divisible par 11.

Et pourquoi pas S₁₃ : n=13=3r+1 avec r=4
S₁₃=3(-p/3²)∑_k'=0¹C₁₃^3k'+2 (u^3k'v^3(3-k')+u^3(3-k')v^3k')
S₁₃=(p²/3)(C₁₃²(v⁹+u⁹)+C₁₃⁵(u³v⁶+u⁶v³))
et, comme ci-dessus
S₁₃=(p²/3)(C₁₃²(-q³-p³q/9)+C₁₃⁵(p³q/27))
S₁₃=(p²/3)(13×6(-q³-p³q/9)+13×11×9(p³q/27))
S₁₃=(p²/3)×13(-6q³-2p³q/3+11p³q/3)
S₁₃=13p²q(p³-2q²).

Allez, encore un, S₁₇ : n=17=3r+2 avec r=5
S₁₇=3(-p/3)∑_k'=0²C₁₇^3k'+1 (u^3k'v^3(5-k')+u^3(5-k')v^3k')
S₁₇=-p(C₁₇¹((v³)⁵+(u³)⁵)+C₁₇⁴(u³v³(u⁹+v⁹))+C₁₇⁷(u⁶v⁶(u³+v³))
Pour alléger, posons a=u³, b=v³ (donc a+b=-q, ab=-p³/27)
S₁₇=-p(C₁₇¹((a+b)⁵-5ab(a+b)³+5(ab)²(a+b))+C₁₇⁴(ab(a+b)³-3(ab)²(a+b))+C₁₇⁷((ab)²(a+b)))
S₁₇=-p(17(a+b)⁵+(-5×17+C₁₇⁴)ab(a+b)³+(17×5-3C₁₇⁴+C₁₇⁷)(ab)²(a+b))
S₁₇=-p(17(a+b)⁵+(17×5×27)ab(a+b)³+(17×27²)(ab)²(a+b))
S₁₇=-p(17(-q)⁵+(17×5×27)(-p³/27)(-q)³+(17×27²)(-p³/27)²(-q))
S₁₇=-17p(-q⁵+5p³q³-p⁶q)
S₁₇=17pq(p⁶-5p³q²+q⁴)

Sur ces exemples correspondants à a=0, on vérifie effectivement que pour n 1er, n divise S_n, mais on constate qu'en fait S_n est un polynôme en p et q dont tous les coefficients sont divisibles par n : le but du chapitre II est justemment d'approfondir cet aspect.

Remarque :
Au cours de cette démonstration, on a mis en évidence une formule explicite pour S_n en fonction de u et v, lorsque n est premier (deux cas à envisager, selon que n≡1 (3) ou n≡2 (3)) ; si n n'est pas premier, des calculs analogues doivent (?) permettre d'obtenir aussi une formule explicite, mais n'en n'ayant pas besoin, je n'ai pas essayé...