Arithmétique : nombres premiers et divisibilité

[lapras]

Bonsoir,
j'ouvre un post que j'utiliserai pour poster tous les exos sympas sur ce theme.
On commence par un exercice tres facile :
"Soit p un nombre premier. Montrer qu'il existe un diviseur premier de p^p - 1 et est congru à 1 modulo p."

[ThSQ]

Intéressant !

Lapras, montre que ça reste vrai même si p n'est pas premier !

(nettement plus corsé ...)

[lapras]

Ma démonstration ne marche que dans le cas p premier car on utilise l'ordre de p modulo q qui est justement p ou 1 et dans le cas ou c'est 1 pour tout q on montre facilement qu'il y a une contradiction.

je vais essayer pour tout nombre entier ca a l'air tres dur !

[ThSQ]

pour tout nombre entier ca a l'air tres dur !

Je me souviens avoir cherché longtemps sans rien trouver et la correction était "waouhhh, gloups". Good luck

[Imod]

Y'en a qui usent et abusent de la transparence , je ne donnerai pas de nom mais je n'en pense pas moins !!!

Imod

[lapras]

Si TOI tu as cherché longtemps comme ca, et que tu trouves ca horriblement dur, je n'ose même pas m'imaginer chercher.

[_-Gaara-_]

@ Imod, il suffit de faire CTRL+A et tout apparaît =)

[ThSQ]

J'ai envie de dire : !

[ffpower]

je plussoie

[aviateurpilot]

salut

pour (puissance d'un nombre premier)
(*) soient un premier divisant tel que et
on a .
soit qui divisera bien sure et donc
on a donc donc
ce qui donne . d'ou
puisque les ne sont qui des puissances de alors donc pour un certain
finalement ce premier verifiant donc

je vais voire le cas de quelconque apres ((je me prepare pour le concours lol))

[_-Gaara-_]

je plus-plussoie

104 101 105 110 32 63 :we:

[lapras]

Quelqun veut il poster la solution à cet exo ?
Personnellement voici la mienne :
soit k le plus petit entier tel que p^k = 1 [mod q], q désignant un diviseur premier de p^p - 1
k est l'odre de p modulo q
pour tout entier a tel que p^a = 1 [mod q], a est un multiple de k
ici on a
p^p = 1 [q]
fermat => p^(q-1) = 1 [q]
donc
d = PGCD(p , q-1) = k
k divise p
donc k = 1 ou p
si k = p pour un certain q c'est fini car p divisera q - 1 donc q = 1 [p]
si k = 1 pour tout q premier divisant p^p - 1, alors
p^k = p = 1 [q]
donc q divise p-1
or
p^p-1 = (p-1)*(p^(p-1) + p^(p-2) + ... + p + 1)
comme p-1 ne divise pas (p^(p-1) + p^(p-2) + ... + p + 1)
on a l'existence d'au moins un x entier premier divisant (p^(p-1) + p^(p-2) + ... + p + 1) et non p-1
en particulier x divise p^p - 1
et x ne divise pas p-1
contradiction

[lapras]

Ok pour la démo aviateurpilot, toujours tres condensé ton LaTex :we:
Bravo !
Il te reste a faire le cas n = p1^alpha1*p2^alpha2*...
Ca a l'air plus compliqué de résoudre ca avec ta méthode :(

[aviateurpilot]

Ok pour la démo aviateurpilot, toujours tres condensé ton LaTex :we:
Bravo !

je voulais montrer le resultat vrai pour tous n au debut,mais quand j'ai trouvé que A=ppcm(des d_q).
alors j'ai pris le cas particulier ou n est une puissance d'un nombre premier pour que ppcm(des d_q)=max des d_p. lol.
je vais chercher pour l'autre cas apres. a+

[lapras]

Oui c'est tres bien joué le coup de PPCM(de tous les d_q) = n
mais ce qui nous arrange c'est que n est une p puissance parfaite puisque dans ce cas les dq sont eux aussi des puissances parfaites...

[lapras]

Nouvel exercice (Russie en 1996) :

Prouver qu’il n’existe pas d’entiers a et b strictement positifs
tels que, pour tous nombres premiers distincts p et q strictement superieurs a 1000, le nombre ap + bq soit aussi premier.

[ffpower]

Pas trop dur celui la... :++:
On fixe p,q premier >1000 avec p>a, et on note p(0)=p et p(n+1)=ap(n)+bq.Tous les p(n) devraient etre censés etre premiers or par reccurence directe on a p(n)=[1+a+...+a^(n-1)]*b*q modulo p =(a^n-1)/(a-1)*b*q modulo p. Comme a^(p-1)=1 modulo p,pour n=p-1 on obtiens un terme divisible par p absurde

[lapras]

Ok c'est une (belle) solution !
Je ne l'avais pas fait comme ca, je l'écrirai ce soir. Elle repose sur le théoreme de dirichlet.

[lapras]

Ma solution :
soit m premier
le théoreme de dirichelt nous dit qu'il existe p premier (meme tres grand) tel que
a*p = 1 [mod m]
de même, il existe q tel que
b*q = -1 [mod m]
donc
a*p + b*q = 0 [mod m] impossible.

[namfoodle sheppen]

oui enfin reste à démontrer le théorème de dirichlet :briques: