Divisibilité.

[invitea5ab8741]

Bonjour,

Je veux montrer que en prenant 7 entiers quelconques, il y en a toujours 4 dont la somme est divisible par 4.

En réfléchissant sur les congruences, si au moins 4 des 7 entiers sont tous congrus à 0, 1, 2 ou 3 [mod 4] alors l'énoncé est vrai.

Ensuite, si 3 des 7 nombres sont congrus à 0 mod 4, alors parmi les quatre nombres qui restent, soit il y en a 2 qui sont congrus à 2 mod 4 donc énoncé vrai, sinon un congru à 1 et un autre à 3 mod 4, donc éoncé vrai.

Bref je peux m'en sortir comme ça mais c'est maladroit.

Est-ce que vous auriez une autre piste à me donner ?
-----

[invite5f67e63a]

Bonjour,
C'est un cas particulier d'un théorème difficile (parmi 2n-1 nombres il en existe n dont la somme est divisible par n)
Donc soit tu veux démontrer ce théorème dans sa generalité. Et dans ce cas la on peut y refelchir, l'idée est de d'abord se ramener au cas ou n est premier. Puis de prouver le resultat dans F_p.
Ici tu peux faire des paquets de 2 pour te ramener a des questions de parité.

[invitea5ab8741]

Soient a,b,c,d,e,f,g 7 entiers pris au hasard.

Parmi trois entiers pris au hasard, il y en a toujours au moins 2 qui sont pairs, ou impairs.
Donc par exemple, parmi a,b et g, on a : a+b congru à 0 [2].
De même parmi c,d et e, on a :
c+d congru à 0 [2]

Donc : soit a+b+c+d congru à 0 [4] et donc l'énoncé est vérifié.
soit a+b+c+d congru à 2 [4] et donc il faut faire encore plusieurs cas ... (même si je précise qu'il y a au maximum parmi les 7 entiers , 3 qui peuvent être congrus entre eux mod 4)

C'est la démo la moins laide que j'ai trouvée.

[invite5f67e63a]

Soient a,b,c,d,e,f,g 7 entiers pris au hasard.

Parmi trois entiers pris au hasard, il y en a toujours au moins 2 qui sont pairs, ou impairs.
Donc par exemple, parmi a,b et g, on a : a+b congru à 0 [2].
De même parmi c,d et e, on a :
c+d congru à 0 [2]

Donc : soit a+b+c+d congru à 0 [4] et donc l'énoncé est vérifié.
soit a+b+c+d congru à 2 [4] et donc il faut faire encore plusieurs cas ... (même si je précise qu'il y a au maximum parmi les 7 entiers , 3 qui peuvent être congrus entre eux mod 4)

C'est la démo la moins laide que j'ai trouvée.

C'est domage, en raffinant a peine ton idée tu peux etre encore plus precis.
Tu regarde d'abord abc, comme tu l'as justement remarqué parmi ces 3 nombres il y en a forcement deux dont la somme est paire.
Disons a et b, alors tu les "mets de coté", puis tu regarde celui qu'il te reste (ici c donc) et tu rajoute les deux suivants, d et e.
Parmi c, d et e, tu en as 2 dont la somme est paire. Tu les mets de coté puis tu prends celui qui reste disons x et tu regarde x,f,g, la encore tu peux en trouver 2 dont la somme est paire.
Tu as donc trouvé 3 paires disjointes {y1,y_2}, {y_3,y_4}, {y_5,y6} tel que les somme des elements de chaque paire soit paire.
Pose z_1=(y1+y_2)/2, z_2=(y_3+y_4)/2, et z_3=(y_5+y_6)/2.
Note que ar construction les z_i sont des entiers.
Mais tu as de nouveau 3 nombres, z_1,2,3, donc tu sais que il en existe deux donc la somme est paire.
Donc z_i+z_j=2k, ce qui donne tes 4 nombres donc la somme est divisible par 4.

[A voir en vidéo sur Futura]

[invitea5ab8741]

Aïe je n'y avais pas pensé ...Merci c'est plus joli !

Maintenant, j'aimerais trouver le plus petit n tel que parmi n entiers, on peut toujours en trouver 8 dont la somme est divisible par 8.
Dans la démontration que tu as postée, j'ai constaté qu'il fallait nécessairement 7 entiers : si par exemple il n'y en avait que 6, la somme de x et f ne serait pas paire et donc (x+f)/2 n'est pas forcément entier.

Je conjecture que donc pour n=8, il y a 2*8-1=15 entiers minimum pour que la proposition soit vérifiée.
Mais à nouveau, problème pour la rédaction de la démonstration...

[invite5f67e63a]

Alors, oui parmi 15 entiers tu pourras en trouver 8 dont la somme est divisible par 8. En fait comme je t'ai dit, ce resultat est vrai pour tout n.
D'ailleurs, tu dois commencer a t'en rendre compte, le travail se fait en deux parties on demontre d'abord le resultat pour n=p, puis on prouve comme precedement en faisaint des paquets que s'il est vrai pour p et q, il est vrai pour pq.
Est ce que c'est optimal...
Je ne sais pas. C'est clairement optimal pour 2 par exemple...
Je ne sais pas si c'est optimal pour tous les nombres n.

[invitea5ab8741]

Je pense que ma conjecture est vérifiée, si je prends sept 1 et sept 2 (=>14 entiers), il est impossible d'en trouver 8 parmi ces 14 là tels que leur somme est divisible par 8.

Plus généralement, si je prend 7 termes congrus à 1 [4] et 7 autres congrus à 2 [4];
ou bien 7 termes congrus à 3 [4] et 0[4];
ou bien 7 termes congrus à 1 [4] et 0 [4];
ou bien 7 termes congrus à 2 [4] et 3 [4];
du moment que la somme des deux congruences n'est pas paire.

[invite5f67e63a]

Oui, c'est correct.

[invitea5ab8741]

Je souhaite maintenant démontrer le théorème général.

D'abord pour n =p premier :

Dans mon dernier post je raisonne sur les congruences.
Alors je considère 2p-1 restes modulo p :

0<r(1)<r(2)<...<r(2p-1) (c'est des inférieurs ou égal et non des inférieurs stricts).

S'il y a p restes égaux au moins, soit : r(i)=r(i+p-1); alors "somme" = p*r(i) congrus à 0 mod p.
S'il n'y a pas p restes égaux, et bah je bloque ....

Pouvez-vous m'aider (ou proposer d'autres idées) ?

[invite5f67e63a]

Je souhaite maintenant démontrer le théorème général.

D'abord pour n =p premier :

Dans mon dernier post je raisonne sur les congruences.
Alors je considère 2p-1 restes modulo p :

0<r(1)<r(2)<...<r(2p-1) (c'est des inférieurs ou égal et non des inférieurs stricts).

S'il y a p restes égaux au moins, soit : r(i)=r(i+p-1); alors "somme" = p*r(i) congrus à 0 mod p.
S'il n'y a pas p restes égaux, et bah je bloque ....

Pouvez-vous m'aider (ou proposer d'autres idées) ?

C'est assez delicat comme resultat.
Voila une démarche que je vous propose.
POsez R_i={r(i),r(i+p)}, pour i=1,...,p-1
Notez que (je note |A| le cardinal d'une partie) si |R_i|=1, pour un certain i, vous avez fini (vu que vos r(i) sont ordonnés).
On est donc ammené a supposer que tous les R_i sont de cardinal 2.
Alors (et c'est le point clé) montrez que |R_1+R_2|>=3, puis que |R_1+R_2+R_3|>=4, et enfin |R_1+...+R_{p-1}|>=p (ici le fait que p soit premier intervient de manière cruciale).
Déduisez en le resultat pour n=p.

[invitea5ab8741]

|R_1+R_2|=|{r(1);r(2);r(1+p);r (2+p)}|.
Si r(1) différent de r(2); on a r(1+p) différent de r(2) car on a supposé qu'il n'y avait pas p restes égaux.
Donc ici la taille est bien supérieure à 3.

Mais si r(1)=r(2); r(1+p) différent de r(2) pour les mêmes raisons, mais rien n'interdit que r(1+p) différent de r(2+p). Donc taille seulement supérieure à 2.

J'ai dû mal comprendre ?

[invite5f67e63a]

Bonsoir,
Par A+B, je ne désigne pas du tout la reunion, mais la somme des ensemble
A+B={a+b|a dans A, b dans B}.
Peut etre est cela qui vous bloquait.

[invitea5ab8741]

Si j'ai bien compris : j'ai : {r(1)+r(2);r(1)+r(2+p);r(1+p)+ r(2);r(1+p)+r(2+p)}.
On a supposé qu'il n'y avait pas p restes égaux, donc r(1)+r(2) est différent de r(1)+r(2+p).
r(1+p) > r(1) et r(2+p) > r(2) donc r(1+p) et r(2+p) est différent de r(1)+r(2).
Il n'y a pas p restes égaux donc : r(1)+r(2+p) est différent de r(1)+r(2).
Donc il y a bien au moins trois éléments distincts.

De la même façon, je prouve que les éléments : r(1)+r(2)+r(3); r(1+p)+r(2)+r(3); r(1+p)+r(2+p)+r(3); r(1+p)+r(2+p)+r(3+p) sont différents.
Donc |{R_1+R_2+R_3}| supérieure (ou égale) à 4.

Enfin, les éléments : r(1)+r(2)+r(3)+...+r(p-1);
r(1+p)+r(2)+r(3)+...+r(p-1);
r(1+p)+r(2+p)+r(3)+...+r(p-1);
r(1+p)+r(2+p)+r(3+p)+...+r(p-1);
...
r(1+p)+r(2+p)+r(3+p)+...+r(2p-1) sont différents.
Donc |{R_1+R_2+R_3+...+R_(p-1)}| supérieure à p.

Je bloque encore...
Il faut utiliser le fait que p soit premier (je suppose) pour montrer que parmi ces p éléments différents, il y en a toujours un qui est divisible par p.

[invite5f67e63a]

Si j'ai bien compris : j'ai : {r(1)+r(2);r(1)+r(2+p);r(1+p)+ r(2);r(1+p)+r(2+p)}.
On a supposé qu'il n'y avait pas p restes égaux, donc r(1)+r(2) est différent de r(1)+r(2+p).
r(1+p) > r(1) et r(2+p) > r(2) donc r(1+p) et r(2+p) est différent de r(1)+r(2).
Il n'y a pas p restes égaux donc : r(1)+r(2+p) est différent de r(1)+r(2).
Donc il y a bien au moins trois éléments distincts.

De la même façon, je prouve que les éléments : r(1)+r(2)+r(3); r(1+p)+r(2)+r(3); r(1+p)+r(2+p)+r(3); r(1+p)+r(2+p)+r(3+p) sont différents.
Donc |{R_1+R_2+R_3}| supérieure (ou égale) à 4.

Enfin, les éléments : r(1)+r(2)+r(3)+...+r(p-1);
r(1+p)+r(2)+r(3)+...+r(p-1);
r(1+p)+r(2+p)+r(3)+...+r(p-1);
r(1+p)+r(2+p)+r(3+p)+...+r(p-1);
...
r(1+p)+r(2+p)+r(3+p)+...+r(2p-1) sont différents.
Donc |{R_1+R_2+R_3+...+R_(p-1)}| supérieure à p.

Je bloque encore...
Il faut utiliser le fait que p soit premier (je suppose) pour montrer que parmi ces p éléments différents, il y en a toujours un qui est divisible par p.

Bonjour,
Tu peux, par reccurence montrer le lemme suivant, si A et B sont des parties de F_p (non triviales).
Alors |A+B|>=|A|+|B|-1, ou triviale.

[invitea5ab8741]

F_p=?
Et la démonstration de mon dernier post n'est pas correcte ?

[invite5f67e63a]

F_p=?
Et la démonstration de mon dernier post n'est pas correcte ?

Bonjour,
F_p désigne Z/pZ (c'est le corps a p elements, c'est plus court a ecrire).
Et dans ton dernier post, je n'ai pas trouvé de démo justement

[invitea5ab8741]

Je crois que je sors de ton raisonnement, mais cela doit être la meme idée...

Si je prends 2 entiers a et b qui ne sont pas congrus entre eux modulo p, et qui ne sont pas congrus à 0 modulo p;
alors a+b n'est ni congru à a ni à b mod p (car a et b pas congrus à 0 mod p).
Donc cela fonctionne pour une liste de deux entiers : il y a en effet au moins 3 classes de congruences.

Je suppose que c'est vrai pour m - 1 entiers.
Montrons que c'est vrai pour m entiers.

Soient x1,x2,...x(k) toutes les classes de congruences de la forme :
Somme(de i=1 à m-1) e(i)*r(i) avec e(i)=0 ou 1 et r(i) un reste de la division euclidienne par p premier.
D'après ci-dessus, forcément k>=m.
Si k > m alors c'est bon.
Si k = m (<p): alors (et là je pense qu'il me manque une justification même si ça me paraît évident) il existe au moins un x(j) avec j allant de 1 à k, tel que :
x(j) + r(m) pas congrus aux autres.
Donc cela fonctionne.

N'hésitez pas à me dire si j'ai fait une chose maladroite ou s'il manque une justification. (C'est sûrement le cas à la fin de ma démonstration.)

[invitea5ab8741]

J'ai oublié de préciser la proposition que je démontre : Pour p>2, si je prends r entiers tous premiers à p (restes non nuls de la division euclidienne par p), avec r(1) pas congru à r(2) mod p (cela est nécessaire pour l'initialisation de la récurrence); alors somme (de i=1 à m) r(i)*e(i) avec e(i) = 0 ou 1; contient au moins m+1 classes de congruences.

C'est pour ça que k>=m dans mon dernier post.
Concernant la justification que j'ai dit qu'il manquait, en fait c'est juste : m < p.

Avec cette proposition, on peut s'attaquer au problème:

Je pose : somme (de i=1 à p) r(i) congrue à c.
(Si c'est congru à 0; alors c'est fini.)

Soit : x(i)=r(i+p-1) - r(i).
(J'ai pris par hypothèse dans des posts plus haut une liste de 2p-1 restes tels que: 0<r(1)=<r(2)...=<r(2p-1). Ici, on prend le cas où il n'y a pas r restes égaux, sinon le théorème est vérifié. D'où : r(i) différent de r(i+p-1).)
Alors d'après la propostion que j'ai démontrée, il existe une : somme (de i=1 à p) e(i)*x(i) congrue à -c; (e=0 ou1)

J'additionne la somme des r(i) et des e(i)*x(i), c'est congru à 0.

Si e(i) = 0 pour i donné, alors on additionne un r(i), si e(i)=1; on a r(i) + x(i) = r(i)+r(i+p-1)-r(i)=r(i+p); on additionne donc ici un r(i+p-1).
Au total, on additionne p restes.

Maintenant, pour n composé.
Je fais un cas particulier qu'on généralisera ensuite.
Je pose n = p*q avec p et q premiers.
Parmi 2pq-1 entiers, j'en prends p dont la somme est congrue à 0 mod p.
On obtient en continuant de cette manière 2q - 1 sommes de p entiers congrues à 0.
Parmi ces 2q -1 sommes, il y en a une qui est congrue à 0 mod q.
Donc cette dernière est congrue à 0 mod pq, c'est-à-dire mod n.

On généralise avec n qui se décompose en produit de facteurs premiers.

Voilà la démonstration du théorème.
Merci de m'avoir donné une idée de départ (notamment la propriété (ou lemme) qui m'a aidée à démarrer).

Faites part de vos commentaires s'il y a des imprécisions ou des erreurs de raisonnement (j'espère qu'il n'y en a pas !)

[invitea5ab8741]

Dans l'énoncé de la proposition, c'est m entiers r, désolé.

[invite5f67e63a]

Bonjour,
Il me semble y avoir une probleme dans votre raisonnement (mais je n'ai lu qu'en diagonale).
Le resultat que je vous propose de démontrer fonction pour p premier, et le fait que p soit premier est clé, or je ne vous vois pas utiliser ce fait (dans Z/4Z, prenez A=B={0,2}, alors |A+B|=2<3=|A|+|B|-1)

[invite5f67e63a]

Ok, en fait apres avoir relu, vous ne démontrez pas la propriété que j'ennonce...
Le passage delicat que vous signalez, ne me semble pas immediat, mais il doit cependant etre vrai (et pas tres dur a prouver)

[invitea5ab8741]

Pour le passage délicat, un raisonnement par récurrence devrait suffire à le démontrer.
En tout cas je pense que vous raisonnez aussi sur les classes de congruences, et alors la démonstration de votre lemme doit être dans le même ordre d'idée.