Salut,

x et y désignent deux nombres entiers strictement positifs.

1) si x = y mod p pour tout premier p, alors x = y

2) Si x <=y mod p pour tout premier p, alors x = y

La 1) est trivialement vraie, qu'en est-il de la 2)?

Heu... Pour la 1), si x = kp, c'est faux.

Grimmys, p étant universel dans les assertions, poser x = kp n'est pas loisible.

Ah.

D'accord, on m'a jamais appris ça mais ok.

Excuse moi alors.

Ca veut dire quoi x <= y mod p ?

Le 12 juin 2016 à 14:22:08 Sylves a écrit :
Ca veut dire quoi x <= y mod p ?

Oui ça mérite définition : cela veut dire que la division de x par p donne un reste inférieur à celui de la division de y par p.

Le 12 juin 2016 à 14:21:58 Grimmys a écrit :
Ah.

D'accord, on m'a jamais appris ça mais ok.

Excuse moi alors.

je trouve que la façon dont amandin l'a expliqué n'est peut-être pas très claire alors je me permets de le réexpliquer

ici x a une valeur fixée, et on a x = y mod p POUR TOUT p premier
si tu poses x = kp, x n'a pas une valeur fixée

Le 12 juin 2016 à 14:32:08 skywear a écrit :

Le 12 juin 2016 à 14:21:58 Grimmys a écrit :
Ah.

D'accord, on m'a jamais appris ça mais ok.

Excuse moi alors.

je trouve que la façon dont amandin l'a expliqué n'est peut-être pas très claire alors je me permets de le réexpliquer

ici x a une valeur fixée, et on a x = y mod p POUR TOUT p premier
si tu poses x = kp, x n'a pas une valeur fixée

D'acccord.
C'est vrai que j'avais du mal à saisir.
Merci.

Ben la 2 est fausse non ?

Montrer que si x <=y mod p pour tout premier p, alors x = y (E)
revient à montrer que
si x =/= y, alors x > y mod p pour tout p premier (F).

En prenant x = 2 et y = 1, on a bien x =/= y, mais on remarque que 2 = 0 [2] et 1 = 1 [2], soit que 2 <= 1 [2] ou encore x <= y [2]. Donc l'implication (F) est fausse, et de même pour la (E).

Non ?

Le 12 juin 2016 à 14:52:28 Sylves a écrit :
Montrer que si x <=y mod p pour tout premier p, alors x = y (E)
revient à montrer que
si x =/= y, alors x > y mod p pour tout p premier (F).

Non, cela revient à montrer que si x =/= y, alors x > y mod p pour au moins un nombre premier p

Montrer que si x <=y mod p pour tout premier p, alors x = y (E)

revient à montrer que
si x =/= y, alors x > y mod p pour tout p premier (F).

Eh non, faille logique élémentaire mais importante. Le contraire de "pour tout [truc], [machin] est vrai" est "il existe [truc_particulier] tel que [machin] soit faux".

Ah oui, mince

Il est clair que si x <= y mod p pour tout p, alors en prenant p un nombre premier plus grand que x et y, on a forcément que x <= y dans N.

Up,

il est clair que a = b dès lors que b possède un facteur premier que a n'a pas (car alors b = 0 < a mod p).

Il reste donc à traiter le cas où a et b possède les mêmes facteurs premiers. J'avance à petit pas car j'ai beaucoup de boulot à côté mais si vous avez des idées...

Ah tu as pas résolu l'exo ? Ben du coup après mon erreur stupide j'y avais réfléchi aussi, et j'avais essayé de prouver que la proposition en question était vraie par contraposée. Du coup avant hier j'en étais arrivé au même stade que toi, pour le cas où x > y ça pose pas de problème, il suffit de prendre un nombre premier p1 > x pour avoir x > y mod p1.

Dans le cas où x < y et où y a un facteur premier que x n'a pas, c'était évident oui. Après j'ai bloqué sur le cas où x et y ont les mêmes facteurs premiers : il faudrait trouver un nombre premier p1 tel que x < p1 < y et tel que x > y mod p1. L'existence d'un nombre premier compris entre x et y est assuré par le postulat de Bertrand, mais on n'a pas d'assurance qu'on ait effectivement x > y mod p1.
Exemple avec x = 2 et y = 8 :
On a bien 2 < 5 < 8, mais on a 2 < 8 mod 5.

Edit : Ou on pourrait trouver p1 < x, ça pourrait aussi aller en fait ptet

J'ai pas tellement d'idée du coup, peut-être qu'il faudrait partir différemment

Salut Sylves et merci de ta réponse.

J'aurais dû préciser que je n'avais pas de démo au moment de poster le topic, cela dit je pense que l'idée de regarder où l'on peut positionner les nombres premiers (ou leurs multiples) est la bonne idée, mais le postulat de Bertrand n'est pas assez fin.

Sur la page wiki, on a une version plus fine :
https://fr.wikipedia.org/wiki/Postulat_de_Bertrand

Parmi n entiers consécutifs, il y a au moins un multiple d'un nombre premier strictement supérieur à n.

Ca permet de régler le cas où y est grand par rapport à x : Si y >> x, en vertu du théorème ci-dessus, on peut trouver un multiple d'un nombre premier p > x dans la suite de x nombres suivants : y ; y - 1 ; y - 2 ; y - 3 ; ..... y - x + 1 (autrement dit, les x nombres consécutifs avant y).

Alors on a clairement x mod p = x et y mod p < x (car y - i = kp pour un certain i € {0, ... x-1} donc y = i mod p < x).

Par exemple si x = 8 et y = 1024, il y a un multiple d'un nombre premier supérieur à 8 parmi les 8 nombres suivants : 1024 1023 1022 1021 1020 1019 1018 1017. En effet, 1023 = 11 × 93.

On a 8 mod 11 = 8 mais 1024 mod 11 = 1 donc 1024 < 8 mod 11.

Le problème est que ça ne fonctionne plus du tout lorsque x et y sont très proches, et Bertrand non plus d'ailleurs.

Donc il reste le cas où x et y sont très proches (et il faut définir proprement "très proches", autrement dit voir dans quels cas ma démo au dessus fonctionne)

peut etre que tout le monde l'avait deja note mais si la decomposition de y en facteur premier est simple alors le resultat est vrai:
pour tout k premier, alors k|y => k|x donc x multiple de y, de plus pour p assez grand le reste des divisions par p de x et y sont eux meme d'ou x <= y donc x=y

Le 14 juin 2016 à 17:35:53 Amandin a écrit :
Donc il reste le cas où x et y sont très proches (et il faut définir proprement "très proches", autrement dit voir dans quels cas ma démo au dessus fonctionne)

Je m'auto-réponds, pour que ce que j'ai fait avec la généralisation de Bertrand fonctionne, il suffit de pouvoir former la séquence y - 1 , y - 2 , .... , y - x + 1 dans N, donc que y soit au moins le double de x.

Le problème est donc résolu dans ce cas, il reste le cas où y est inférieur au double de x.

Ben c'est pas possible puisque si x et y ont les mêmes facteurs premiers et que x < y on a nécessairement "au moins" y = 2x, 2 étant le plus petit nombre premier (et à ce moment là le postulat de Bertrand marche aussi).

C'est cool ce que t'as fait ! Par contre je vois pas où tu trouves sur la page wiki que "Parmi n entiers consécutifs, il y a au moins un multiple d'un nombre premier strictement supérieur à n."

Il y a bien "Le produit de k entiers consécutifs supérieurs à k est divisible par un nombre premier plus grand que k.", mais à ce moment là faudrait ajouter la condition que les n entiers consécutifs sont supérieurs à n non ?

Ben c'est pas possible puisque si x et y ont les mêmes facteurs premiers et que x < y on a nécessairement "au moins" y = 2x

Malheureusement non, par exemple avec x = 12 et y = 18, ils ont bien les même facteurs premiers.

Sinon oui,tu as raison il faut bien rajouter que les nombres doivent être supérieurs à n (et c'est d'ailleurs pour ça que ça ne fonctionne que si y > 2x)