Exercices de MPSI

[Retard]

Sur le papier j'ai une idée maintenant le traduire pour python :s ...

Tu connais la récursivité ?

[lsjduejd]

Tu veux faire quoi, les afficher ? Faire une fonction qui demande un chiffre entre 1 et n! et qui répond par la permutation n°i ?

[lsjduejd]

J'ai trouvé un exo d'arithmétique sympa :

Soient :
$ \bullet $ $ P_n $ le produit des $ n $ premiers nombres premiers (la primorielle) $ = p_1p_2p_3 ... p_n $ avec $ p_1 = 2 $, $ p_2 = 3 $, $ p_3 = 5 $, $ ... $
$ \bullet $ $ p_{n+1} $ le $ (n+1)^{ieme} $ nombre premier,
$ \bullet $ $ Q_n $ le produit de $ n $ nombres premiers impairs $ = q_1q_2 ... q_n $

$ 1) $ Démontrer que pour $ n $ quelconque, $ P_n + 1 $ ne peut jamais être un carré parfait.
$ 2) $ Démontrer que pour $ n $ quelconque, $ Q_n^2 + 1 $ ne peut jamais être un cube parfait.
$ 3) $ Pour quelles valeurs de $ n $ a-t-on $ P_n >p_{n+1}^2 $ ?
$ 4) $ Démontrer que pour $ n > 1 $, $ P_n - 1 $ ne peut jamais être une puissance parfaite.

On pourra utiliser le fait que pour $ n $ dans $ \Bbb N $, il existe un premier compris strictement entre $ n $ et $ 2n $. (Postulat de Bertrand)

Voili, voilo (sauf erreur) :

La 1 :

SPOILER:

Supposons $ P_{n}+1=q^2 $
Alors comme P_n est pair, q est nécessaire impair, donc : $ P_n=(q-1)(q+1) $
Or q-1 est q+1 sont pairs, donc $ P_n $ est multiple de 4, ce qui est absurde !

La 2 :

SPOILER:

Supposons : $ Q_{n}^2+1=c^3 $
Comme $ Q_{n} $ est impair, $ c^3 $ est pair et donc multiple de 8.
On a donc : $ Q_n^2\equiv7[8] $.
En étudiant les congruences modulo 8, on se rend compte que c'est absurde, ce qui conclut.

La 3 :

SPOILER:

Procédons par récurrence, soit à partir d'un certain rang $ P_{n}>p_{n+1}^2 $ avec $ p_{n+1}>4 $.
Alors, d'après le postulat de Bertrand, on a : $ p_{n+1}<p_{n+2}<2p_{n+1} $
soit : $ p_{n+1}^2<p_{n+2}^2<4p_{n+1}^2<P_{n+1} $
L'hérédité est ainsi démontrée. Et la proposition est amorcée à partir du rang 4 (car $ p_5=11 $ et $ 11^2<7*5*3*2=210 $).

L'inégalité n'est donc fausse que pour : n=1 avec $ p_1=2 $, n=2 avec $ p_2=3 $, n=3 avec $ p_3=5 $ et n=4 avec $ p_4=7 $

La 4 :

Faute spotted :

SPOILER:

Supposons : $ P_{n}-1=a^q $, on en déduit que pour tout i dans [1,n], on a : $ a^q\equiv-1[p_i] $

I - En étudiant les congruences [3], on déduit que a est impair et $ a\equiv2[3] $ et surtout que q est impair.

II - De plus, en factorisant, on trouve : $ P_{n}=(a+1)(\sum_{i=0}^{2k}(-1)^i*a^i) $.

III - Montrons la propriété A: "$ p_{i}/q $ implique $ p_{i}\wedge (a+1)=1 $".

Procédons par contraposée et supposons $ p_{i}/(a+1) $
Alors $ a\equiv -1[p_{i}] $. Or $ P_{k}=(a+1)(\sum_{i=0}^{2k}(-1)^i*a^i) $, donc $ \sum_{i=0}^{2k}(-1)^i*a^i\wedge p_{i}=1 $. Or $ \sum_{i=0}^{2k}(-1)^i*a^i\equiv q[p_{i}] $. Finalement, $ q\wedge p_{i}=1 $. La propriété est donc démontrée.


IV - Supposons maintenant l'existence d'un premier $ p_i<p_n $ qui divise q :

On aurait donc :$ p_{i}/q $ donc $ q=c*p_{i} $ avec c impair.


Alors, d'après le petit théorème de Fermat, comme $ a^{c*p_{i}} \equiv a^c[p_{i}] $, on a :
$ a^c\equiv -1[p_{i}] $. Du coup, $ p_{i} $ divise $ a^c+1 $ avec c=2c'+1.

Du coup comme $ a^{2c'+1}+1=(a+1)(\sum_{i=0}^{2c'}(-1)^i*a^i) $, et d'après la propriété A, $ p_{i} $ divise $ \sum_{i=0}^{2c'}(-1)^i*a^i $ et $ p_{n+1}\wedge (a+1)=1 $.

Or $ p_{i}<p_n $ divise $ P_{n}=(a+1)(\sum_{i=0}^{2k}(-1)^i*a^i) $, donc $ p_{i} $ divise $ \sum_{i=0}^{2k}(-1)^i*a^i $.

Du coup, $ p_{i} $ divise $ \sum_{i=0}^{2k}(-1)^i*a^i-\sum_{m=0}^{2c'}(-1)^m*a^m $ d'où $ p_{i} $ divise $ \sum_{i=2c'+1}^{2k}(-1)^i*a^i=a^{2c'}*\sum_{i=1}^{2k-2c'}(-1)^i*a^i $.

On remarque de plus que : $ \sum_{i=1}^{2k-2c'}(-1)^i*a^i=(a-1)*\sum_{i=1}^{k-c'}a^{2i-1} $.

Or $ p_{i}>2 $ et $ p_{n+1}\wedge (a+1)=1 $, donc $ p_{n+1}\wedge (a-1)=1 $.

Ainsi, $ p_{i} $ divise $ \sum_{i=1}^{k-c'}a^{2i-1} $ et divise $ a*\sum_{i=1}^{k-c'}a^{2i-1} $ et divise donc leur somme : $ \sum_{i=1}^{2k-2c'}a^{i} $.

Donc, $ p_{i} $ divise $ a^{2c'}*\sum_{i=1}^{2k-2c'}a^{i}=\sum_{i=c}^{2k}a^{i} $. Or $ p_{n+1} $ divise $ a^c+1 $ donc $ p_{n+1} $ divise $ \sum_{i=0}^{c-1}a^{i} $.

Finalement de finalement : $ p_{i} $ divise $ \sum_{i=0}^{2k}a^{i} $, or (on revient au début ) :
$ P_{n}-2=a^q-1=(a-1)(\sum_{i=0}^{2k}a^{i}) $ donc $ p_{i} $ divise $ P_n-2 $ et est par conséquent premier avec $ P_n $ ou vaut 2 (mais alors q serait pair (ce qui est absurde pour n>1)).


On en déduit donc que $ q=c*p_i $ avec $ p_i>p_n $ et donc que $ q>p_n>n $.
Ainsi, en supposant $ a>p_n $ : $ a^q>a^n>p_n^n>P_n>P_n-1 $ ce qui est absurde. Du coup $ a<p_n $. Or a n'est divisible par aucun des premiers composant $ P_n $, ce qui est absurde.

Finalement, $ P_n-1 $ ne peut jamais être une puissance parfaite pour n>1.

[Galileo Galilei]

La 4 :

Faute spotted

SPOILER:

Supposons : $ P_{n}-1=a^q $, on en déduit que pour tout i dans [1,n], on a : $ a^q\equiv-1[p_i] $

I - En étudiant les congruences [3], on déduit que a est impair et $ a\equiv2[3] $ et surtout que q est impair.

II - De plus, en factorisant, on trouve : $ P_{n}=(a+1)(\sum_{i=0}^{2k}(-1)^i*a^i) $.

III - Montrons la propriété A: "$ p_{i}/q $ implique $ p_{i}\wedge (a+1)=1 $".

Procédons par contraposée et supposons $ p_{i}/(a+1) $
Alors $ a\equiv -1[p_{i}] $. Or $ P_{k}=(a+1)(\sum_{i=0}^{2k}(-1)^i*a^i) $, donc $ \sum_{i=0}^{2k}(-1)^i*a^i\wedge p_{i}=1 $. Or $ \sum_{i=0}^{2k}(-1)^i*a^i\equiv q[p_{i}] $. Finalement, $ q\wedge p_{i}=1 $. La propriété est donc démontrée.


IV - Supposons maintenant l'existence d'un premier $ p_i<p_n $ qui divise q :

On aurait donc :$ p_{i}/q $ donc $ q=c*p_{i} $ avec c impair.


Alors, d'après le petit théorème de Fermat, comme $ a^{c*p_{i}} \equiv a^c[p_{i}] $, on a :
$ a^c\equiv -1[p_{i}] $. Du coup, $ p_{i} $ divise $ a^c+1 $ avec c=2c'+1.

Du coup comme $ a^{2c'+1}+1=(a+1)(\sum_{i=0}^{2c'}(-1)^i*a^i) $, et d'après la propriété A, $ p_{i} $ divise $ \sum_{i=0}^{2c'}(-1)^i*a^i $ et $ p_{n+1}\wedge (a+1)=1 $.

Or $ p_{i}<p_n $ divise $ P_{n}=(a+1)(\sum_{i=0}^{2k}(-1)^i*a^i) $, donc $ p_{i} $ divise $ \sum_{i=0}^{2k}(-1)^i*a^i $.

Du coup, $ p_{i} $ divise $ \sum_{i=0}^{2k}(-1)^i*a^i-\sum_{m=0}^{2c'}(-1)^m*a^m $ d'où $ p_{i} $ divise $ \sum_{i=2c'+1}^{2k}(-1)^i*a^i=a^{2c'}*\sum_{i=1}^{2k-2c'}(-1)^i*a^i $.

On remarque de plus que : $ \sum_{i=1}^{2k-2c'}(-1)^i*a^i=(a-1)*\sum_{i=1}^{k-c'}a^{2i-1} $.

Or $ p_{i}>2 $ et $ p_{n+1}\wedge (a+1)=1 $, donc $ p_{n+1}\wedge (a-1)=1 $.

Ainsi, $ p_{i} $ divise $ \sum_{i=1}^{k-c'}a^{2i-1} $ et divise $ a*\sum_{i=1}^{k-c'}a^{2i-1} $ et divise donc leur somme : $ \sum_{i=1}^{2k-2c'}a^{i} $.

Donc, $ p_{i} $ divise $ a^{2c'}*\sum_{i=1}^{2k-2c'}a^{i}=\sum_{i=c}^{2k}a^{i} $. Or $ p_{i} $ divise $ a^c+1 $ donc [FAUTE ICI ] $ p_{i} $ divise $ \sum_{i=0}^{c-1}a^{i} $.

Finalement de finalement : $ p_{i} $ divise $ \sum_{i=0}^{2k}a^{i} $, or (on revient au début ) :
$ P_{n}-2=a^q-1=(a-1)(\sum_{i=0}^{2k}a^{i}) $ donc $ p_{i} $ divise $ P_n-2 $ et est par conséquent premier avec $ P_n $ ou vaut 2 (mais alors q serait pair (ce qui est absurde pour n>1)).


On en déduit donc que $ q=c*p_i $ avec $ p_i>p_n $ et donc que $ q>p_n>n $.
Ainsi, en supposant $ a>p_n $ : $ a^q>a^n>p_n^n>P_n>P_n-1 $ ce qui est absurde. Du coup $ a<p_n $. Or a n'est divisible par aucun des premiers composant $ P_n $, ce qui est absurde.

Finalement, $ P_n-1 $ ne peut jamais être une puissance parfaite pour n>1.

J'ai failli commencer à lire, en prenant mon courage à deux mains. Heureusement que tu l'as repérée avant .

[lsjduejd]

Je pressentais bien que y'allait avoir une bêtise... Bon, j'abandonne cette question, je sèche comme un phoque hors de l'eau, je la laisse à d'autres.

[omamar3131]

SPOILER:

Tu peux essayer de voir ce qui se passe pour les puissances $ a^p $ avec $ p $ premier puis généraliser.

[JeanN]

Un revenant !

[omamar3131]

Ça commençait à me manquer, je faisais un petit tour afin de dénicher quelques jolis exercices.

[JeanN]

Un grand nombre ont été compilés ici très récemment par KGD
http://www.2shared.com/document/pUfCVye ... _exos.html
Bonne lecture !

[omamar3131]

Merci et la prochaine!