problème en arithmétique

[invite949a348a]

Bonsoir,

Si on a trois entiers naturels n,p,q avec p premier, n=pq et q strictement compris entre 1 et n, qu'est ce qui fait qu'on a p inférieur ou égal à q?
Ca me bloque pour une démo...

Merci!
-----

[zenxbear]

soit précis. avec les élements donnés, ton truc n'a pas de sens.
6=3x2, 3>2
42=7 x 6 . 7>6

[invite949a348a]

1)Je voudrais montrer que tout entier naturel n non premier admet un diviseur premier p inferieur ou égal à la racine carrée de n, sachant qu'on a déjà prouvé que tout entier naturel supérieur ou égal à 2 admet un diviseur premier.

2)Je profite de ce fil pour poser une autre question d'arithmétique,concernant l'algorithme d'Euclide cette fois : Si au lieu de remplacer PGCD(a;b) par PGCD(b;r) à la ligne suivante, on remplaçait PGCD (a;b) par PGCD(r;b), cela fonctionnerait il?
Je sais que PGCD(a;b)=PGCD(b,r)=PGCD (r,b) en notant r le reste de la division euclidienne de a par b, ce que je veux comprendre c'est pourquoi on utilise tel sens de l'égalité et pas l'autre .

Merci

[Resartus]

Bonjour,
Pour la première question, on peut toujours rebaptiser p et q pour appeler q le plus grand des deux (ou égal). et p sera alors le plus petit ou égal.

Pour la deuxième, il n'y aucune différence, puisque quels que soient x et y, pgcd(x,y)=pgcd(y,x) : c'est comme quand on écrit 3*2 au lieu de 2*3.
Par contre, dans l'algorithme d'euclide, comme on va commencer par diviser le plus grand par le plus petit, on met le plus grand en premier (donc b dans ce cas) car c'est l'ordre usuel pour écrire une division b/r

[A voir en vidéo sur Futura]

[invite949a348a]

1) je n'ai pas bien compris : p et q sont "fixés" à l'avance(j'ai explicité davantage au message 3)
2)je suis d'accord, mais pourquoi on utilise toujours PGCD(b,r) et pas PGCD(r,b)?
Parce que b est plus grand que r?

Merci pour la réponse en tout cas

[zenxbear]

1/ si p est premier divise n. tu as écris
a/si q est plus grand que p, ton problème est résolu. car
b/ Si q<p. Soit q vaut 1. donc n=p est premier.
Soit Il admet des facteurs premier différents de 1. on a trouvé q' premier différent de 1, qui divise q. et j'ai
et j'ai trouvé mon diviseur premier inférieur à

C'est pas vrai pour tous les diviseurs premier de n. Par exemple

2/ C'est plus clair visuellement. On te fait un clin d'oeil pgcd(le minimum de a et b, le reste de la division euclidienne du maximum entre a et b avec le minimum de a et b).

C'est un algorithme itératif, à l'étape suivante que vas tu faire? va tu diviser r par b our b par r?

Si tu les écris en chaine, qu'est ce qui est plus clair visuellement:
Pgcd(a,b)= pgcd(b, c) = pgcd (c ,d) = pgcd (d , e)....

avec
c reste de division de a par b.
d reste de division de b par c
e reste de division de c par d.

ou l'écrire
Pgcd(a,b)= pgcd(c, b) = pgcd (c ,d) = pgcd (e,d)....

[invite949a348a]

J'ai bien compris pour la 2) mais pas vraiment pour la 1) .
Voilà la démonstration qui me pose problème:soit p premier qui divise n.Il existe donc un entier q tel que n=pq avec 1<q<n .
Donc q est un diviseur propre de n et par conséquent p est inférieur ou égal à q. On en déduit que p^2 est inférieur ou égal à pq et on conclut bien que p est inférieur ou égal à racine de n.
Voilà précisément ce que je ne comprends pas : Le 1<q<n et le "par conséquent p est inférieur ou égal à q".

[zenxbear]

tu lis en diagonale. Je n'ai pas dis "q est un diviseur propre de n et par conséquent p est inférieur ou égal à q".

Ce que tu cherches à démontrer est "si n n'est pas premier, alors il admet un diviseur premier inférieur à ".
Et non pas "si n n'est pas premier alors TOUT diviseur premier est inférieur à ".

J'ai même souligne à 2 fois que pour n=6, et si on pose p=3, bein p est plus grand que et est plus petit que p.

Relis ce que j'ai écris. Il y a une condition SI. Une étude de cas. "si p est plus petit que q je fais..." et "si p est plus grand que q je fais ..."

[invite949a348a]

Justement, je n'ai pas compris tes explications, donc j'ai repris la démonstration de mon livre en ciblant ce que je ne comprends pas. La démonstration que j'ai recopiée ci-dessus est la démonstration du livre, pas la tienne
Et j'aimerais comprendre celle de mon livre, dans la progression du chapitre ca me semble plus cohérent.

Peux-tu donc m'expliquer cette démonstration du livre? Dans mon message précédent, j'ai recopié la démonstration et ciblé les deux points qui me posent un problème.

[zenxbear]

ca

soit p premier qui divise n.Il existe donc un entier q tel que n=pq avec 1<q<n .
Donc q est un diviseur propre de n et par conséquent p est inférieur ou égal à q.

c'est pas complet comme démonstration. Il manque quelque chose. par exemple "p est le plus petit nombre premier qui divise n".

Je répète, si je pose n=6, et p =3. p divise n. Mais q=2 et q < p!

[invite949a348a]

Pourtant je n'ai que ça...n est non premier,mais ça je l'ai déjà dit. Et cette demo prend appui sur le fait que tout entier naturel supérieur ou égal à 2 admet un diviseur premier.je n'ai rien d'autre :/