bonjour
on me demande de montrer que tout entier non nul s'écrit comme un produit de nombres premiers
Alors je n'arrive pas a trouver la relation de récurrence qui va me permettre de faire l'exercice
j'avais pensé a : b=q*p ou p et q sont deux nombres premiers et a un entier mais alors il va étre impossible de montrer cela par récurrence
Donc si quelqu'un aurait la moindre idée
je suis preneur
d'avance merci
bonne soirée
soit b un entier non nul, on veut montrer qu'il possède une décomposition en facteurs premiers.
1) On peut choisir un de ses diviseurs différent de 1 et de b. Si y'en a pas, b est un nombre premier donc décomposition finie.
2) On a le diviseur m qu'on vient de choisir. On appelle n l'entier tel que b = m*n; Remarquons que m,n < b (strictement). La décomposition de b est la même que celles de m et n multipliées.
3) On recommence à 1) pour m et n
En fait on retient tous les nombres premiers qui sont passés par 1) : c'est la décomposition qu'on cherche!
On sait que cette procédure est finie par m,n < b.
edit:
Cette solution utilise pas de récurrence... dsl si c'est nécessaire...
disons que si on sait que tout nombre n tq |n| < k €Z est décomposable, on peut faire une récurrence en s'inspirant de
On a le diviseur m qu'on vient de choisir. On appelle n l'entier tel que b = m*n; Remarquons que m,n < b (strictement). La décomposition de b est la même que celles de m et n multipliées.
Salut,
Korgox, ça me semble incomplet. Ne faudrait-il pas démontrer que, lorqu'on décompose, au bout d'un certain nombre de décompositions (quand on décompose encore m, et n, puis qu'on décompose les facteurs de m et n...), on trouve des facteurs premiers? Je ne crois pas que tu le fasses.
Je pense en effet qu'on pourrait démontrer ça par récurrence en supposant que tous les nombres <=n vérifient la propriété, puis démontrer qu'alors elle est vérifiée pour (n+1). Je vais y réfléchir, mais pour l'instant dodo.
c'est la definition d'une demonstration par récurrence! Mais je pense que tu vas avoir un peu de mal à demontrer que si cette propriété est vrai au rang n alors elle l'est au rang n+1, mais ça doit forcement être faisable si ils le demandent...
exemple de piste:
supposons n=p*q vrai
montrons que n+1=p'*q' avec p' et q' premiers
n+1=p*q+1
=p*q+u*p+q*v (u et v dans Z, th de Bezout)
=p*(q+u)+qv ... et là je suis bloqué... mais bon c'est à developper.... je penses que ça peut marcher.
non?
mais bon là c'est pas le moment de chercher ça... c'est l'heure de dormir!!
++
Salut,
voilà ce que je propose:
Il faut démontrer que tout entier non nul s'écrit comme un produit de nombres premiers. Je ne résouds ça que dans N puisque les nomres premiers sont tous positifs, donc un nombre négatif ne peut pas être le produit de nombres premiers.
Supposons que tous les entiers naturels de 1 à n soient le produit de nombres premiers.
Alors:
1er cas: Si (n+1) est premier, alors (n+1) s'écrit bien sous la forme d'un produit de nombres premiers (mais il faut pour cela considérer 1 comme premier, c'est implicite dans le problème).
2ème cas: Si (n+1) est pair, alors (n+1) peut s'écrire sous la forme ((n+1)/2)*2. Par hypothèse, (n+1)/2 peuts'écrire comme le produit de nombres premiers, et 2 est premier, donc (n+1) peut s'écrire comme le produit de nombres premiers.
3ème cas: Si (n+1) est impair non premier, alors (n+1) peut s'écrire comme le produit de deux nombres impairs (différents de 1) inférieurs à n, donc qui sont le produit de nombres premiers. Donc (n+1) est le produit de nombres premiers.
Voilà, il faut aussi que je montre qu'un nombre impair non premier est forcément le produit de deux nombres impairs. Soit k un nomre impair et p et q deux facteurs tels que p*q=k (p, q dans N existent forcément si k non premier). Alors, si p ou q est pair, k peut s'écrire sous la forme 2a=k, donc k est pair. Donc pour que k soit impair, il faut que p et q soient impairs.
Bon, maintenant, il reste à montrer que la propriété est vraie pour 1, c'est trivial si on considère que 1 est premier.
Qu'en pensez-vous?
coucou moi aussi j'y vais de ma petite proposition : déja si seule l'existence est demandée c'est pas le plus dur ; ) l'unicité est un peu moins drôle (pas insurmontable qd même) . Donc donc : Si on montre que tout entier >= 2 admet au moins un diviseur premier c'est gagné par récurrence ! . Or il suffit de remarquer que pour a >=2 , k = min {x dans N / x|a et x >= 2} est premier .(immédiat par l'absurde ! ) (heu au cas ou x|a signifie x divise a )
bon et bien, c'est assez difficile de démontrer une proposition erronéeon me demande de montrer que tout entier non nul s'écrit comme un produit de nombres premiers
contre exemple : 1
1 est un entier non nul mais n'est pas un produit de nombres premiers. (car 1 n'est pas premier)
si c'est un devoir et que t'as le courage tu réponds ça et on ne peut pas te donner tord. un nombre premier est divisible par 1 et par lui-même (admet exactement 2 diviseurs)
Dernière modification par olle ; 14/11/2004 à 11h09.
pour moi la solution de korgox est correcte...
je sais pas si c'est de la récurrence, mais c'est en tout cas de la récursivité.
il n'y a aucun rapport entre n et n+1 dans cet exo.
Oui, la solution de Korgox est bien je trouve... par contre tu pourrais m'expliquer ce qu'est la récursivité s'il te plait olle? J'ai jamais entendu ce mot...
merci
je sais pas trop si les termes sont bien choisis, mais la récursivité c'est :
- le cas de base où la démonstration est généralement triviale
- les autres cas que peuvent se décomposer en sous cas
ici la proposition est "A peut se mettre sous forme de produit de nombres premiers":
cas de base : "A est un nombre premier"
cas général : "A est le produit de B avec C"
et là on relance la règle pour B et C, car si B et C sont des produits de nombres premiers, A l'est par conséquence aussi.
si B n'est pas premier, on le subdivise en D et E... etc etc jusqu'à n'avoir que des nombres premiers (cas de base)
c'est comme la récurrence, sauf qu'on n'est pas limité par le (n+1) par rapport à n... c'est plus freestyle
je sais pas si c'est clairc'est hyper utilisé en info
Ben.. si. On arrete la décomposition d'un nombre p que s'il est premier (alors p = p, c'est la décomposition de p et pas p = 1*p d'ailleurs... p = p est la bonne décomposition). Et un nombre quelconque a on continue de choisir deux de ses diviseurs m,n tq m*n = a. En fait on continue de prendre des diviseurs jusqu'à tomber sur un nombre premier. La propriété la moins évidente de la construction c'est qu'elle est finie....Envoyé par Sharp
Salut,
Korgox, ça me semble incomplet. Ne faudrait-il pas démontrer que, lorqu'on décompose, au bout d'un certain nombre de décompositions (quand on décompose encore m, et n, puis qu'on décompose les facteurs de m et n...), on trouve des facteurs premiers? Je ne crois pas que tu le fasses.
Cela dit c'est pas très beau qd même comme démo ^^'
Remarques :
- Sur Z, -3 est premier. La définition d'un nbre premier est juste différente (a€Z est premier ssi a possède 4 diviseurs(distincts) exactement)
- 1 n'est pas premier.
Par récurrence :
Hypothèse : la propriété est vérifiée pour tout a € Z, |a| < b
Soit b est premier, alors décomposition finie.
Sinon on choisit deux diviseurs m,n de b tq |m|,|n| différents de b et de 1 et m*n = b.
On a |m|,|n| < b => m et n possèdent une décomposition.
Or, la décomposition de b est la même que celles de m et n multipliées (il suffit d'écrire m, n comme produit de nombre premiers, on a alors b exprimé comme un produit de nbre premiers, c'est ce qu'on veut). => b est aussi décomposable.
-2 et 2 sont décomposables donc tout nombre est décomposable (sauf -1, 0 et 1)
K2R RiDdiM>
Pourquoi suffit-il de monter que tout nombre admet un diviseur premier ? Je suis prêt à te croire, mais c'est plutot opaque là ?_?
EDIT:
Ah merci olle et FrB d'avoir soutenu ma réponse ^^' j'avais pas posté mon message quand je l'avais écrit O_O (je l'avais écrit juste après la réponse de K2R)
Merci pour la réponse olle, c'est très clair (non non c'est pas une blague.). C'est comme tu l'as dits une récurrence libre en gros.... ça me parait avoir ses avantages sans ses inconvénients.... je sens que ça va servir à mon prochain ds de math ça
++
Wui j'ai été un peu court j'avoue : donc on a démontré que tout nombre >=2 admet au moins un diviseur premier . alors recurrons maintenant ; )
2 s'ecrit bien en produit de facteur(s) premier(s).
Supposons le réusltat établit pour tt k entier naturel plus petit que n (récurrence forte).
Alors par ce qui précede il existe p premier qui divise n : n= p* m et on applique l'hypothese de recurrence a m : c'est gagné ! a mon sens c'est la dem "la plus courte " si tan est que ceci veuille dire qqchose : )
Salut,
hum, c'est ce que 'jai fait dans ma démo... Dans ma démo, il faudrait juste que je rectifie que 1 n'est pas premier (donc le premier terme est 2, et pour ce que j'ai appelé le 1er cas, on n'a pas besoin de dire que 1 est premier, puisque si n est premier, n s'écrit bien comme le produit de nombres premiers).2 s'ecrit bien en produit de facteur(s) premier(s).
Supposons le réusltat établit pour tt k entier naturel plus petit que n (récurrence forte).
Alors par ce qui précede il existe p premier qui divise n : n= p* m et on applique l'hypothese de recurrence a m : c'est gagné ! a mon sens c'est la dem "la plus courte " si tan est que ceci veuille dire qqchose : )
Ma démo est-elle valable??
Quels sont les diviseurs premiers d'un nombre :des nombres premiers,ton entier naturel s'ecrit comme produit de puissances de ces diviseurs premiers,donc comme produit de nombres primairesuissances de nombres premiers(theoreme fondamental)
wuiwui ca marche tt seul : ) mais ct juste poru signaler qu'efait on a pas besoin de faire de cas , c'est toujours ca de gagner . mais au dela y'a pas de pb c tt aussi juste : ). D'ailleurs si vous avez envie de prolonger le truc chercher a démontrer l'unicité (a l'ordre des facteurs pres bie nsur) de cette decomposition .
Oui oui, c'est bien ce qu'on demande de prouver...Quels sont les diviseurs premiers d'un nombre :des nombres premiers,ton entier naturel s'ecrit comme produit de puissances de ces diviseurs premiers,donc comme produit de nombres primaires
Salut,
On demande justement de le démontrer!Quels sont les diviseurs premiers d'un nombre :des nombres premiers,ton entier naturel s'ecrit comme produit de puissances de ces diviseurs premiers,donc comme produit de nombres primaires
Ok! Pour l'unicité, on peut également appliquer la récurrence, non?wuiwui ca marche tt seul : ) mais ct juste poru signaler qu'efait on a pas besoin de faire de cas , c'est toujours ca de gagner . mais au dela y'a pas de pb c tt aussi juste : ). D'ailleurs si vous avez envie de prolonger le truc chercher a démontrer l'unicité (a l'ordre des facteurs pres bie nsur) de cette decomposition .
comme un échoSalut,
On demande justement de le démontrer!
Si tu veux dire qu'on garde la même démo mais qu'on rend l'hypothèse légérement plus forte comme :
tt nbre plus petit que k admet une, et une seule, décomposition en facteurs premiers
et que tu espere utiliser ça pour prouver que k+1 possède une seule décomposition aussi, alors pas du tout ^^'
il me semble me rappeler que c'est pas trop dur par l'absurde par contre...
Pour l'unicité:
soit a le plus petit entier décomposable de deux manières :
a = produit(pi) = produit(qi)
on a pi différent de qj pour tout i,j sinon on pourrait simplifier par pi (ou qj donc) des deux cotés et on aurait un entier plus petit que a décomposable de deux manières.
On peut poser p1 < q1 sans perdre de généralité...
Division euclidienne :
q1 = d*p1 + r ou q1/p1 = d + r/p1 avec r < p1 et d > 0
donc
a/p1 = produit[i différent de 1](qi) * (d + r/p1) = produit(qi)*d + r/p1*produit(qi)
comme a/p1 entier, produit(qi)*d entier, on a k=r/p1*produit(qi) entier également.
k*p1 = r * produit(qi) < a
on s'accroche encore un peu; on peut décomposer k et r, et comme r < p1, la décomposition de r ne comporte pas p1 et on a qi différent de p1. DONC on a deux manières de décomposer un nombre plus petit que a de deux manières, puisque le nombre premier p1 n'apparait pas à droite de l'égalité. Ca contredit l'hypothèse
=> décomposition unique. Alleluia !
re coucou . Ca me rapelle un truc rigolo que j'ai vu cette année , si ca interesse quelqu'un d'y réflechire un peu : on a donc montrer qu'on peut decomposer n entier naturel comme produit de nombres premiers , mettons p premier apparait dans cette decomposition , a la puissance k . Alors k est appelé valuation p-adique de n , noté vp (n) . Voici donc la question : Quelle est la valuation p-adique de n! ?
Il faut trouver k pour tous les facteurs p? Si oui, étant donné que n peut avoir une infinité de facteurs lorsqu'il tend vers l'infini...
c'est plutot pour un n donné et p premier quelle est la valuation p-adique de n! ?
Ok. Hmmm, ça m'a pas l'air facile quand même...
En fait pour bien partir : Soit n entier naturel et k <=n ,il s'agit d'abord de trouver le nombre de multiples de k inférieurs ou égaux à n. Apres ca roulera pas mal : )
Salut,
en passant, je vous livre le premier résultat de la recherche sous google avec pour mots-clefs "théorème fondamental de l'arithmétique":
http://villemin.gerard.free.fr/ThNbCo01/ThFoDemo.htm
Salut !
Ce site m'a l'air très intéressant et complet... En plus, l'auteur est un ingénieur INSA Lyon, comme moi dans un peu moins de 3 ans !
