Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
49 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

démonstration lemme d'Euclide

Envoyé par t3tesla 
démonstration lemme d'Euclide
il y a dix années
Bonjour,

Dans une démonstration du lemme d'Euclide, il me reste à montrer le point suivant :

"Soit $p$ un nombre premier et soient $\alpha$ et $\beta$ des
entiers tels que $0<\alpha<p$ et $0<\beta<p$. Alors, $p$ ne divise pas $\alpha\beta$."

J'ai une preuve dans le traité de Gauss, les Disquisitiones arithmeticae.
Mais j'aimerais me raccrocher et utiliser le théorème vu en terminale S :
"Si $n$ (supérieur ou égal à 2) n'est pas premier, il admet au moins un diviseur premier $p$ tel que $p\leq \sqrt{n}$."
En effet, j'ai la vague impression que ces deux propositions peuvent être proches (étant donné que $\sqrt{\alpha\beta}<\sqrt{p^2}=p$)....

Une idée ? merci.
AD
Re: démonstration lemme d'Euclide
il y a dix années
avatar
Bonjour Tesla

Et tout simplement $ 0<\alpha<p$ donc tous les diviseurs premiers de $\alpha$ sont strictement $< p$, idem pour $\beta$, donc aussi pour le produit $\alpha.\beta$ (dont les diviseurs premiers sont la réunion des diviseurs premiers de chacun des facteurs)

Alain
Re: démonstration lemme d'Euclide
il y a dix années
Ce sujet est souvent ambigu, parce que les gens considèrent évident "la factorialité" de $\Z$ et le prouve avec

En fait, je pense que scientifiquement, c'est plutôt l'autre sens qui est acceptable faut d'abord prouver la div euclidienne (ce qui n'est pas dur) et ENSUITE prouver ton lemme:

Soit $u,v$ tel que $ua+vp=1$



Si $ab=rp$ alors en multipliant par $b$ tu obtiens $b=uab+vpb=urp+vpb=p(ur+vb)$ et donc $p$ divise $b$. Avec les valeurs absolues ça te donne que $b$ est négatif ou $b=0$ ou $b\geq p$

Pour l'existence de $u,v$ tu prends le plus petit nombre entier positif non nul qui soit de la forme $ua+vp$ et en divisant euclidiennement $p$ par ce nombre, tu obtiens que ça ne peut être que $1$.
Re: démonstration lemme d'Euclide
il y a dix années
Pardon AD, je n'avais pas vu: mais tu supposes connu que la factorisation en premiers d'un entier est unique, non?

Or pour justifier qu'elle est unique, n'a-t-on pas tellement d'autre moyen que d'utiliser l'énoncé de Tesla?

Qu'elle existe est plu simple, je pense, mais l'unicité?
Re: démonstration lemme d'Euclide
il y a dix années
Merci de vos réponses.

J'ai oublié de préciser le contexte de ma preuve :
Je souhaite démontrer le lemme d'Euclide sans utiliser le lemme de Gauss, ni le théorème de Bachet-Bézout.
Je suis arrivé au point du premier poste juste en utilisant quelques bases sur la divisibilité (division euclidienne/congruences).
Re: démonstration lemme d'Euclide
il y a dix années
Citation

Je souhaite démontrer le lemme d'Euclide sans utiliser le lemme de Gauss, ni le théorème de Bachet-Bézout.

Que de noms savants... Perso je ne connais pas les théorèmes (leur association aux noms)

Es-tu satisfait des réponses?
Re: démonstration lemme d'Euclide
il y a dix années
Citation

Que de noms savants... Perso je ne connais pas les théorèmes (leur association aux noms)
Il est vrai que les deux savants cités ont fait beaucoup de "lemmes". Je précise donc :

Lemme d'Euclide : Si un nombre premier $p$ divise le produit de deux nombres entiers $b$ et $c$, alors $p$ divise $b$ ou $c$.

Lemme de Gauss : Si un nombre entier $a$ divise le produit de deux autres nombres entiers $b$ et $c$, et que $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

Théorème de Bezout : Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $x$ et $y$ tels que $ax+by=1$.

Je cherche à démontrer le lemme d'Euclide sans utiliser le lemme de Gauss (celui cité ci-dessus ;)), ni le théorème de Bezout.
En effet, le lemme d'Euclide parait élémentaire et ne nécessite que la définition de "diviseur" pour être énoncé. Je me demandais donc s'il est nécessaire d'introduire le pgcd (via Bezout) pour le montrer.

J'ai suivi ta réponse jusqu'au "en divisant euclidiennement $p$ par ce nombre"... Je me suis alors dit qu'on était en train de démontrer Bezout, et que ma question initiale n'avait peut être pas grand sens...

Bonne fin de soirée.
nicoh
Re: démonstration lemme d'Euclide
il y a dix années
A vérifier
Par l'absurde :
Notons p le plus petit premier capable de diviser un produit de 2 facteurs sans diviser aucun de ces 2 facteurs

Parmi tous les produits de 2 facteurs que p divise sans diviser aucun des 2 facteurs considérons le plus petit (#) : ab (minimal !) avec a et b non divisibles par p.

a et b coïncident nécessairement avec leur reste dans la div euc par p ( en notant ra et rb ces restes, ils sont non nuls et p divise ra rb...) donc a et b appartiennent à [1,p-1]

p divise ab donc il existe n tel que pn=ab (*)

n=0 ou 1 est impossible (..) donc n est divisible par au moins un nombre premier p' (résultat plus élémentaire que la décomposition en produit de facteur premier)

p' ne peut diviser ni a ni b sinon en simplifiant (*) par p' on contredirait (#)

p' divise ab sans diviser ni a ni b donc p'>=p puis pn>=p^2 or ab<=(p-1)^2 contradiction
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 137 394, Messages: 1 330 182, Utilisateurs: 24 423.
Notre dernier utilisateur inscrit AndreR98.


Ce forum
Discussions: 5 097, Messages: 61 840.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page