propriété de récurrence

thor_asgard · 13/11/2004, 18h10

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

Korgox · 13/11/2004, 19h15

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.

Sharp · 13/11/2004, 23h11

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.

FrB · 13/11/2004, 23h37

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!!

++

Sharp · 14/11/2004, 09h31

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?

K2R RiDdiM · 14/11/2004, 11h26

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 )

olle · 14/11/2004, 12h06

Citation:

on me demande de montrer que tout entier non nul s'écrit comme un produit de nombres premiers

bon et bien, c'est assez difficile de démontrer une proposition erronée

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)

olle · 14/11/2004, 12h14

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.

FrB · 14/11/2004, 13h44

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

olle · 14/11/2004, 14h06

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 clair

c'est hyper utilisé en info

Korgox · 14/11/2004, 14h13

Citation:

Posté 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.

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....

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)

FrB · 14/11/2004, 14h31

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

++

K2R RiDdiM · 14/11/2004, 14h34

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 : )

Sharp · 14/11/2004, 20h18

Salut,

Citation:

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 : )

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).
Ma démo est-elle valable??

ulrich richarovitch · 14/11/2004, 20h31

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

uissances de nombres premiers(theoreme fondamental)

K2R RiDdiM · 14/11/2004, 20h32

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 .

Korgox · 14/11/2004, 21h06

Citation:

Posté par ulrich richarovitch

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

uissances de nombres premiers(theoreme fondamental)

Oui oui, c'est bien ce qu'on demande de prouver...

Sharp · 14/11/2004, 21h25

Salut,

Citation:

Posté par ulrich richarovitch

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

uissances de nombres premiers(theoreme fondamental)

On demande justement de le démontrer!

Citation:

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 .

Ok! Pour l'unicité, on peut également appliquer la récurrence, non?