Mathématiques - Arithmétique : nombres premiers et divisibilité

Arithmétique : nombres premiers et divisibilité
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: 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."

Posted by: ThSQ

Intéressant !

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

(nettement plus corsé ...)

Posted by: 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 !

Posted by: ThSQ

Citation:

Posté par lapras

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

Posted by: 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

Posted by: 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.

Posted by: _-Gaara-_

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

Posted by: ThSQ

Citation:

Posté par Imod

$\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\, \,$

J'ai envie de dire : $\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\, \,$ !

Posted by: ffpower

je plussoie

Posted by: aviateurpilot

salut

pour $n=p^a$ (puissance d'un nombre premier)
(*) soient $q$ un premier divisant $n^n-1$ tel que $q^{m}||n^n-1$ et $d_q=ord_{q^{m}}(n)$
on a $d_q|pgcd(n,\varphi(q^m))=pgrc(n,q-1)$ .
soit $A=ppcm(tous\ les\ d_q)$ qui divisera $n$ bien sure et donc $A\le n.$
on a donc $n^A\equiv 1[n^n-1]$ donc $n^n-1|n^{A}-1.$
ce qui donne $n\le A$ . d'ou $A=n.$
puisque les $d_q$ ne sont qui des puissances de $p$ alors $A=max(d_q)=n$ donc $n=d_q$ pour un certain $q$
finalement ce premier $q$ verifiant $n=d_q|pgcd(n,q-1)|q-1$ donc $q\equiv 1[n]$

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

Posted by: _-Gaara-_

je plus-plussoie

104 101 105 110 32 63

Posted by: 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

Posted by: lapras

Ok pour la démo aviateurpilot, toujours tres condensé ton LaTex

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

Posted by: aviateurpilot

Citation:

Posté par lapras

Ok pour la démo aviateurpilot, toujours tres condensé ton LaTex

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+

Posted by: 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...

Posted by: lapras

Nouvel exercice (Russie en 1996) :

Citation:

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.

Posted by: 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

Posted by: 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.

Posted by: 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.

Posted by: namfoodle sheppen

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

Posted by: ffpower

Ouais lol.dans le cas 1 je crois que ya une solution pas trop dure,le cas -1 che pas

Posted by: lapras

Oui c'est vrai ce n'est pas une solution tres glorieuse : j'utilise simplement un théoreme tres puissant tres difficile a démontrer a ce qu'il parait.
Mais j'ai aussi une démonstration plutot longue qui ne demande aucune connaissances je la posterai ce soir.

Posted by: namfoodle sheppen

en fait je crois que le cas modulo p avec p premier est possible pour le théorème de dirichlet ....

Posted by: aviateurpilot

j'ai fait la meme chose que ffpower
mais j'ai fait aussi une autre solution long mais jolie

supposons que $E=\{(a,b)\in\mathbb{N}^*^2:\ a,b \ verifier\ la \ proprieté\}$ est non vide.
soit $p,q\ge 1000$
on a $(a^2+b^2)p+2abq=a(ap+bq)+b(aq+bq)$ est premier
donc $(a^2+b^2,2ab)\in E$
on prend alors la suite $(a_n,b_n)\in E$ tel que $(a_{n+1},b_{n+1})=(a_n^2+b_n^2,2a_nb_n)$ et $(a_0,b_0)=(a,b)$
$a_{n}+b_n=(a_{n-1}+b_{n-1})^2=....=(a+b)^{2^{n}}$
$a_{n}-b_n=(a_{n-1}-b_{n-1})^2=....=(a-b)^{2^{n}}$
donc $b_n=\frac{(a+b)^{2^n}-(a-b)^{2^n}}{2}$

le nombre de ferma $F_4=2^{2^4}+1>1000$ est premier (culture general , lol)
si $F_4\not|a^2-b^2$
alors $F_4|b_{2^4}$ car $(a+b)^{F_4-1}\equiv (a-b)^{F_4-1}\equiv 1[F_4]$
et on a $F_4|qb_{2^4}+F_4a_{2^4}$ qui doit etre premeir (absurde)

si $F_4|a^2-b^2$
$ap+bq\equiv a(p-q)[F_4]$ ou $ap+bq\equiv a(p+q)[F_4]$ et on peut tjrs trouver $p,q >1000$ tel que $p=q[F_4]$ ou $p\equiv -q[F_4]$ (car les premiers sont infini)
ce qui donnera l'absurdité

donc $E$ est vide

Posted by: ffpower

Joli en effet

Posted by: Imod

En voilà un très amusant :

On sait tous que :

- Tout nombre entier possède un multiple qui ne s'écrit qu'avec des chiffres 1 et des 0 ( en base 10 ) .

- Si cet entier n'est divisible ni par 2, ni par 5, il possède un multiple qui ne s'écrit qu'avec des chiffres 1 .

Sauriez-vous montrer que toute puissance de 2 possède un multiple ne s'écrivant qu'avec des 1 et des 2 ?

Bon courage

Imod

Posted by: lapras

salut aviateurpilot la démonstration élémentaire et longue dont je parlais n'est autre que la tienne, on a fait la même a peu de choses pres.
Bravo encore c'est tres beau.

Posted by: aviateurpilot

Citation:

Posté par lapras

salut aviateurpilot la démonstration élémentaire et longue dont je parlais n'est autre que la tienne, on a fait la même a peu de choses pres.
Bravo encore c'est tres beau.

ils ont utilisé $F_4$ ??
mais pour la remarque de $(a_n,b_n)$ est n'est pas tres tres caché

Citation:

Posté par Imod

- Tout nombre entier possède un multiple qui ne s'écrit qu'avec des chiffres 1 et des 0 ( en base 10 ) .

on prend $A\in \mathbb{N}$
on prend $U_n=\frac{10^n-1}{9}$
il exists forcement $i> j$ tel que $U_i\equiv U_j[A]$
donc $U_i-U_j=111....1110000....000$ est un multiple de $A$

Citation:

Posté par Imod

- Si cet entier n'est divisible ni par 2, ni par 5, il possède un multiple qui ne s'écrit qu'avec des chiffres 1 .

dans ce cas $pgcd(A,10)=1$
et donc $\frac{10^{\varphi(A)-1}}{9}=111.....111$ est un multiple de $A$

Citation:

Posté par Imod

Sauriez-vous montrer que toute puissance de 2 possède un multiple ne s'écrivant qu'avec des 1 et des 2 ?

(ce probleme est deja posté,et j'ai deja posté une solution ,la voilà)

soit la proprieté $(p_n):$ "il exists $k_n$ tel que $2^nk_n$ ne contient que des 1e te des 2 et $k_n$ pair ou bien $\frac{5^{n-1}}{2}\le k_n<5^n$ "
$2=2.1$ donc $(p_1)$ vrai
supposons que $(p_n)$ est vrai
il existe donc un $k_n$ tel que $k_n2^n$ ne contient que des 1 et des 2.
si $k_n$ est paire $k_{n}2^{n}+2.10^{n} =2^{n+1}(\frac{k_n}{2}+5^{n})$ multiple de $2^{n+1}$ ne contient que des 1 et des 2 et $k_{n+1}=\frac{k_n}{2}+5^n\in[5^n/1,5^{n+1}[$
si $k$ est impaire $k_n2^n+10^{n}=2^{n+1}(\frac{k_n+5^n}{2})$ multiple de $2^{n+1}$ ne contient que des 1 et des 2.
et $k_{n+1}=\frac{k_n+5^{n}}{2}\in[5^{n}/2,5^{n+1}[$
donc $(p_{n+1})$ est vrai.

(j'ai utilisé le fait que $k_n\in[5^{n-1}/2,5^n [$ pour que $k_{n}2^{n}+a_i10^n=\overline{a_ib_1b_2....b_n}^{(1 0)}$ avec $\overline{b_1b_2....b_n}^{(10)}=k_n2^{n}$ )

Posted by: lapras

Oui j'ai utilisé la transformation mais je n'ai pas fait F4
En fait si (a, b) est un couple de E, alors
PGCD(a, b) = 1
et tout diviseur premier de a et de b est < 1000
or on construit par la transformation (a, b) -> (a² + b², 2ab)
apres on peut prouver tres facilement que PGCD(a_i , a_j) = 1 si i différent de j et que la suite des a_i est strict. croissante.
c'est impossible puisque tout diviseur premier de a sont < 1000

Posted by: Imod

Bien vu Aviateur , je pensais l'exercice original . A peine une heure pour trouver solution c'est vraiment trop peu

Imod

Posted by: lapras

Citation:

Soit n >= 1 un entier. Prouver que parmi 2n − 1 entiers,
on peut toujours en trouver n dont la somme est divisible par n.

Bon courage

Posted by: ThSQ

Citation:

Posté par lapras

Bon courage

Ouais là il en faut ....

( je connais et c'est pas trivial )

Posted by: lapras

C'est un lemme d'erdos.

Oui c'est pas évident !

Posted by: ThSQ

Citation:

Posté par lapras

C'est un lemme d'erdos.

Oui c'est pas évident !

En général Erdös rime avec pas évident (et joli !)

Posted by: lapras

je vais essayer de donner des indices car c'est vrai que c'est un exercice plutôt chaud...
-Montrer que si c'est vrai pour n et m alors c'est vrai pour m*n
-Montrer que c'est vrai pour tout n = p premier

Posted by: Ruch

Merci pour les indices lapras, pour le moment, je n'ai trouvé qu'une réponse plutôt littéraire à la 1ère étape (indice, il faut considérer les 2nm -1 entiers, puis enlever les n entiers de départ et étudier les 2mn-1-n qui restent. Après, il faut utiliser le pgcd...).

Par contre, je n'arrive pas à prouver pour n=p premier.

Posted by: lapras

Ok c'est ca pour la 1ere étape...
Fait une démonstration claire maintenant

(tu as évoqué les PGCD j'attend que tu développes un peu ^^)