théorème d'arithmétique

[invite8d54258a]

Bonsoir ! Je découvre les joies de l'arithmétique, et essaye de prouver les théorèmes suivant :

Si , alors admet diviseurs ;

Si et et alors ;

Ce que j'ai écrit jusqu'à présent n'est pas glorieux Pouvez-vous me mettre sur la piste ? Merci !
-----

[MMu]

Récurrence selon ...

[invite4ef352d8]

Salut !

quand tu as la décomposition en facteur premier de n=P1^ai ... Pk^ak

alors tous les diviseur de n s'obitennent en formant P1^b1*...*Pk^bk, où les bi sont n'importe quelles entier entre 0 et ai.


les deux résultats que tu énoncé, découle assez facilement de cette observation : réfléchi s'y !

[invite8d54258a]

C'est donc bien une récurrence ! Est-ce une récurrence forte ou simple ? Je ne sais pas sur quoi je vais récurrer

[A voir en vidéo sur Futura]

[SchliesseB]

le premier c'est du dénombrement
un diviseur de a s'ecrit p1^h1*p2^h2*...*pk^hk avec les hi choisit entre 0 et ai
il suffit de montrer que j'obtient bien tous les diviseurs comme ça (et que j'obtient pas deux fois le même)
alors j'en ai (a1+1)*(a2+a)*...*(ak+1) (nombre de choix pou h1* nombre de choix pour h2...)

apres pour le second:
en posant p le produit de droit (p^minimum)
montre que p divise a et p divise b
puis montre que tous diviseurs de a et b divise p
tu pourras alors conclure.

[invite8d54258a]

Merci pour le premier, j'ai bien compris !
Pour le second, soit .

On va prouver que et et ainsi divisera .

On écrit .

Il faut alors prouver que divise l'un des ?

[SchliesseB]

non ça c'est faux

on veut montrer que p divise a tout entier. et comme min(ai,bi)<ai ....

de part la question différente: comment s'ecris un diviseur de a? et de b?
et donc s'il divise les deux?

[invite8d54258a]

Je crains de n'avoir compris la démonstration. Puisque , on a et donc d'où .

On utilise bien le fait que la relation de divisibilité dans (et même dans ?) est une relation d'ordre ... totale ? Donc (pour des entiers) ?

On montrera de même que donc .

Maintenant, si , alors et . Ainsi, et et donc et donc il divise p.

[SchliesseB]

wow! stop non!
2<3 donc 2 divise 3?!

la divisibilité n'est pas totale. je peux pas comparer 2 et 3 par exemple.

de même le reste est faux.

pi^mini(ai, bi) divise pi^ai donc le produit de ceux de gauche divise le produit de ceux de droite...

ensuite, suppose que x divise a et b et montre que x divise le produit des pi puissance min(ai,bi)

[invite8d54258a]

Désolé d'avoir raconté que des conneries !
car :

soit et alors c'est bon ;
soit et alors et donc (relation d'ordre dans , non total donc !) il existe tel que , donc d'où .

De même :


...


Et en multipliant terme à terme (j'espère que je dis pas de bêtise encore !) on trouve :
, autrement dit .

De même, et donc .


Réciproquement, si alors donc il existe un tel que . Et de même, il va exister un tel que . Mais je doute que cela implique qu'il divise , puisque j'ai d'un côté le minimum sur l'indice i et de l'autre le minimum sur l'indice j

[SchliesseB]

plein d'erreur et la même!
si b est plus petit que a, rien ne te dis que b divise a, c'est faux!
donc un tel k n'existe pas
par contre, si a>b, a=b+k avec k positif (entier)
alors p^a=p^b*p^k (et oui..p^(k*b) ne fait pas p^k*p^b..regle élémentaire des puissances) et donc la fin est bien juste.

maintenant
soit un diviseur commun de a et b qu'on va noter x
x divise a
x est donc un diviseur de a: il s'ecrit x=Produit(pi^mi) avec les mi plus petit que les ai (tu l'as dis a la question précédente!)
de même x divise b donc les mi sont aussi plus petit que les bi
et donc en fait les mi sont plus petit que les min(ai,bi)
et donc (comme tu as fait ci dessus) x divise p

ainsi tout les diviseurs a la fois de a et de b divise p. donc le pgcd de a et de b aussi (qui est un diviseur de a et b)

ainsi p divise le pgcd et le pgcd divise p
donc p est le pgcd (car les deux sont positifs)

CQFD

pour ça, faut "sentir" le truc:

un nombre peut être decomposer en produit de nombre premier (de maniere unique a l'ordre pres blabla)
par exemple
44352=2^6*3²*7*11
2520=2^3*5*7*3²

on peut ecrire (pour reprendre les données de ton énoncé)
44352=2^6 * 3² * 5^0 * 7^1*11^1
2520=2^3 * 3²*5^1*7^1*11^0

on pose p=produit(pi^minimum(ai,bi))=2 ^3*3²*5^0*7^1*11^0=504
p divise bien 44352 et 2520, ça se voit directement sur la decomposition en facteur premier

(exemple: 44352=2^6*3²*7*11=(2^3*3²*7)*1 1*2^3=504*11*2^3 )

ainsi p divise les deux

puis un diviseur de 44352 et de 2520 s'ecrit
2^a * 3^b * 5^c * 7^d*11^e

pour qu'il divise 44352=2^6 * 3² * 5^0 * 7^1*11^1
il faut (et suffit) a plus petit que 6, b plus petit que 2 .....
idem pour 2520
et donc au final, il doit etre plus petit que min(6,3)=3....
et donc divise p!

p est donc bien le pgcd!

(ps: tu n'as pas de cours d'arithmétique?)

[invite8d54258a]

plein d'erreur et la même!
si b est plus petit que a, rien ne te dis que b divise a, c'est faux!
donc un tel k n'existe pas

Oui, j'ai confondu depuis deux jours ! C'est !

par contre, si a>b, a=b+k avec k positif (entier)
alors p^a=p^b*p^k (et oui..p^(k*b) ne fait pas p^k*p^b..regle élémentaire des puissances) et donc la fin est bien juste.

J'ai compris ! Merci !

maintenant
soit un diviseur commun de a et b qu'on va noter x
x divise a
x est donc un diviseur de a: il s'ecrit x=Produit(pi^mi) avec les mi plus petit que les ai (tu l'as dis a la question précédente!)
de même x divise b donc les mi sont aussi plus petit que les bi
et donc en fait les mi sont plus petit que les min(ai,bi)
et donc (comme tu as fait ci dessus) x divise p

ainsi tout les diviseurs a la fois de a et de b divise p. donc le pgcd de a et de b aussi (qui est un diviseur de a et b)

ainsi p divise le pgcd et le pgcd divise p
donc p est le pgcd (car les deux sont positifs)

CQFD

J'ai complètement oublié la première partie ou vous m'aviez dit que tout diviseur de s'écrit avec . Mais finalement pourquoi ?

Si , alors pour un certain entier . Faut-il utiliser l'unicité de la décomposition en facteurs premiers ? D'un côté j'ai et de l'autre .

Alors par unicité, pour chaque , . Un diviseur de s'écrit donc avec .

pour ça, faut "sentir" le truc

C'est ce que j'ai essayé de faire ci-dessus !
Pour la fin, j'ai parfaitement compris
PS : j'ai pas de "vrai" cours, j'essaye de me débrouiller :/ Votre aide est précieuse !

[SchliesseB]

oui, unicité de la decomposition en facteur premier (en les classant dans l'ordre croissant blabla...)

votre démo est parfaite.
Il faudrait juste expliquer pourquoi vous prenez les mêmes pi pour t, d et a (et le même k). ce qui est toujours possible en ajoutant des puissances nulles

Ex:
18=2*3²=6*3
6=2*3
3=2^0*3
ici les pi sont 2 et 3 et k=2 même pour 3 lorsque je l'ecris 2^0*3.

[invite8d54258a]

OK, votre exemple est très parlant
Du coup, je me suis dit pourquoi ne pas essayer de prouver qu'il y a effectivement existence et unicité de la décomposition en produits de facteurs premiers ?

Pour tout entier , il existe nombres premiers et entiers tous non nuls tel que .

L'existence, par récurrence forte :
il existe tous non nuls et nombres premiers tel que .

, est vraie ;

si , alors l'hypothèse récurrente assure l'implication.
si , il admet au moins un diviseur premier, d'où pour un certain entier et premier . Donc et donc et même (car sinon, et or est premier).
Via l'hypothèse de récurrence, on va pouvoir écrire qu'il existe tous non nuls et nombres premiers tel que et donc .


Je ne suis pas certain de la récurrence forte, mais cela me paraît bon. Qu'en dîtes-vous ?


Pour ce qui est de l'unicité, je n'y arrive pas. Une récurrence encore ?

[SchliesseB]

la récurrence est sur n, pas sur k
pour passer de n a n+1, savoir que k est plus petit que n ne t'avance en rien...

suppose la propriété vrai pour tout n de 2 à m
alors:
soit m+1 est premier et....
soit m+1 n'est pas premier, et donc s'il s'écrit m+1=r*q avec r et q plus petit que m (r et q sont plus grand que 2) et donc la, je peux utiliser mon hypothese de récurrence (sur r et q plus petit que m) (ce que tu as bien fait..mais la condition n'est pas sur k mais bien sur la primalité de m+1)
l'argument de récurrence porte bien sur n et pas k

et sinon rien ne te dis que p ne fait pas partie des p1,p2 etc..donc faut dire qu'on le range au bonne endroit...

l'unicité
p1^a1*....pn^an=q1^b1....qm^bm
montre que p1^a1 divise le membre de droite et tu devrais en conclure qu'un certain qi est egale a p1 avec bi>a1
de même dans l'autre sens etc etc.... c'est juste chiant a écrire...
http://fr.wikipedia.org/wiki/Théorèm...27arithmétique

[invite8d54258a]

Euh, la récurrence forte ne marche pas ? J'ai bien montré que si cela marche pour tous entiers entre 2 et n, ça marche pour les entiers entre 2 et n+1. Je fais bien une récurrence sur n il me semble.

:
s'il existe une décomposition pour les entiers entre 2 et 3, alors il en existe une pour les entiers entre 2 et 4, non ? C'est alors acquis pour les entiers entre 2 et 3, et il reste à le prouver pour l'entier 4.

C'est ce que j'ai comme principe de récurrence forte dans le cours. Je ne sais pas si son utilisation est appropriée !

et sinon rien ne te dis que p ne fait pas partie des p1,p2 etc..donc faut dire qu'on le range au bonne endroit...

Donc j'écris et on arrange cette dernière écriture suivant que est ou n'est pas dans la liste des nombres premiers . Quoiqu'il en soit, c'est toujours une décomposition en produit de facteurs premier.


Sinon, la démonstration de l'unicité ne m'a pas du tout convaincu sur wiki

[SchliesseB]

oui pour la fin


oui recurrence forte mais la phrase:
"si , alors l'hypothèse récurrente assure l'implication." est totalement fausse puisque ta propriété est (supposée) vraie entre 0 et n, mais ce n'est pas k qui importe...
il faut distinguer deux cas: n+1 premier ou pas. si n+1 est premier c'est direct ok, si n+1 ne l'est pas, tu le divise en deux nombre plus petit et là tu utilises ta récurrence forte.

d'ailleurs,
dans ta propriété de récurrence, enleve le quelque soit k etc....car, d'un c'est faux (décompose moi 2 avec 2 nombre premier) et de deux ça n'apporte rien.
P(n)" au rang n, il existe des nombres a1,a2,....ak tous non nuls et des nombres premiers p1, p2,...pk tel que n=produit(pi^ai)."

pour l'unicité:
par réccurence forte aussi si tu veux
suppose que n+1=produit(pi^ai)=produit(qi^ bi)
montre que forcément, p1 est aussi dans le membre de droite (Lemme de Gauss) et donc tu peux diviser par p1 et obtenir des nombres plus petit...la récurrence fait le reste.

[invite8d54258a]

J'ai pas bien compris.
Montrer que : on va prouver que est vraie.

Donc on veut prouver que , on a etc. J'ai bien le droit de distinguer suivant que ou que , non ?

[SchliesseB]

la propriété ecrite comme ça (avec le quelque soit k) est fausse.

de plus ta propriété porte sur n et pas k
savoir que k est inférieur a n ne t'apporte strictement rien.

relis mon message precedent (et le lien wiki)

[invite8d54258a]

O.K., je crois avoir compris le souci. Merci !