Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 27-11-2015 08:40:35

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Un cas praticulier de Fermat.

Bonjour à tous.

Le titre pourrait aussi s'appeler: "Le cinquième élément" ....

On sait que si a est premier avec b, a^phi(b)=1 modulo b phi(b) étant le nombre de nombres premiers avec b compris entre 1 et b-1. On sait aussi que phi(b)=b(1-1/p1)(1-1/p2)...p1, p2, ...étant les nombres premiers entrant dans la décomposition de b.

Partant de là, on en déduit que:
3^(2^n)=1 modulo 2^(n+1).

Prouver maintenant que : 
3^(2^n)=1 modulo 2^(n+2) mais =/=1 modulo 2^(n+3)
pour tout n > 0

Bon amusement



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 28-11-2015 20:19:31

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Un cas particulier de Femrat.

Un indice: la solution passe par l'analyse du binôme (1+2)^2n.
Avec celui que j'ai déja donné....

 #3 - 29-11-2015 20:06:42

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

un cas particulier de fermzt.

On doit prouver que pour tout entier [latex]n\geq 1[/latex], il existe un entier impair  [latex]a_n[/latex] tel que
[TeX]3^{2^n}=1 + a_n\,2^{n+2}[/TeX]
Prouvons-le par récurrence. La relation est vraie pour n=1 car
[TeX]3^2 = 9 = 1+1\times 2^3[/TeX]
Supposons la relation vraie pour un entier [latex]n\geq 1[/latex] fixé. Alors
[TeX]3^{2^{n+1}}=(3^{2^n})^2[/TeX]
[TeX]3^{2^{n+1}}=(1 + a_n\,2^{n+2})^2[/TeX]
[TeX]3^{2^{n+1}}=1 + a_n\,2^{n+3}+ a_n^2\,2^{2n+4}[/TeX]
[TeX]3^{2^{n+1}}=1 + ( a_n+ a_n^2\,2^{n+1} )\,2^{n+3}[/TeX]
On pose [latex]a_{n+1}=a_n+ a_n^2\,2^{n+1}[/latex] qui est bien impair.

La récurrence est terminée !

 #4 - 02-12-2015 17:05:04

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Un cas partiuclier de Fermat.

Voici une autre preuve.
On veut prouver la propriété suivante, pour tout [latex]n\geq 1[/latex] :

l'entier [latex]3^{2^{n}}-1[/latex] est divisible par [latex]2^{n+2}[/latex], mais pas par [latex]2^{n+3}[/latex].

La propriété est vraie pour [latex]n = 1[/latex] car [latex]3^{2^{1}}-1 = 8[/latex].
Supposons que la propriété soit vraie pour un [latex]n\geq 1[/latex] fixé.
Il vient
[TeX]3^{2^{n+1}}-1 = (3^{2^{n}})^2-1 = (3^{2^{n}}-1)\,(3^{2^{n}}+1)[/TeX]
On applique l'hypothèse de récurrence au 1er facteur du second membre.
Pour le 2ème facteur on a [latex]3^{2^{n}}+1 \equiv (-1)^{2^{n}}+1 \equiv 2\mod 4[/latex] car [latex]n\geq 1[/latex].
Donc le 2ème facteur est divisible par 2 mais pas par 4.
Il s'en suit que [latex]3^{2^{n+1}}-1[/latex] est divisible par [latex]2^{n+3}[/latex], mais pas par [latex]2^{n+4}[/latex].
Voilà !

 #5 - 02-12-2015 18:20:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Un cas paticulier de Fermat.

Bravo Masab pour ces 2 belles preuves.
Curieusement , j'avais fait une réponse à ta 1ère preuve, mais elle n'a pas été enregistrée....
La preuve à laquelle je pensais est encore différente, moins directe.
Dans l'expression (1+2)^(2^n), le 5ème terme est toujours impair modulo 2^(n+2). Le 1er terme est 1, la somme des second et troisième est paire et le 4ème est pair même modulo. Tous les termes au delà du 5ème sont pairs.
A part le 1, il n'y a donc qu'un seul impair modulo 2^(n+2). Donc l'expression 3^(2^n) -1 n'est pas divisible par 2^(n+3).

 #6 - 03-12-2015 17:24:29

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Un cas partiulier de Fermat.

La méthode que tu proposes semble commencer par un développement
[TeX](1+2)^{2^n}-1 \equiv \sum_{k=1}^{n+2}C_{2^n}^k\,2^k \mod 2^{n+3}[/TeX]
Après je ne vois pas comment tu procèdes. Que fais-tu des coefficients binomiaux ?

 #7 - 03-12-2015 17:55:01

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Un cas partiuclier de Fermat.

En effet, je n'ai pas détaillé.
(1+2)^(2^n)=
1+
(2^n)*2+
(2^n)*(2^n-1)/(1*2)*2²+
(2^n)(2^n-1)(2^n-2)/(1*2*3)*2^3+
(2^n)(2^n-1)(2^n-2)(2^n-3)/(1*2*3*4)*2^4+
.....

Regroupons les 2 ème et 3 ème termes :
(2^(n+1))(1+2^n-1)=2^(n+1)*2^n est bien pair modulo 2^(n+2).

Maintenant pour les coeff:
C(2^n,a)=(2^n)(2^n-1)---(2^n-a+1)/(1*2*...a)

Or pour tout 1<k<a, (2^n-k) et k ont même puissance de 2. La puissane de 2 de C(2^n,a) est donc celle de 2^n/a. 

Pour le 4 ème terme on en déduit: 2^(n+4) comme puissance de 2, donc coeff pair modulo 2^(n+2).
Pour le 5ème terme: 2^(n+2) comme puissance de 2----->coeff impair modulo 2^(n+2).

Pour les autres termes, on trouve facilement qu'ils sont tous pairs modulo 2^(n+2).

J'avais trouvé ça remarquable, d'où l'énigme proposée.

 #8 - 08-12-2015 15:07:44

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 679

Un cas paticulier de Fermat.

Avec l'idée de nodgim, on peut donner une preuve plus rapide.
On a pour [latex]n\geq 1[/latex]
[TeX]3^{2^n} = (-1+4)^{2^n} =\sum_{k=0}^{2^n} (-1)^k\,C_{2^n}^k \,2^{2k}[/TeX]
Comme l'a indiqué nodgim, le terme d'indice [latex]k[/latex] admet le facteur [latex]2^{n+2\,k-v_2(k)}[/latex]  ; [latex]v_2(k)[/latex] désigne l'exposant du facteur [latex]2[/latex] dans [latex]k[/latex].
Or pour [latex]k\geq 2[/latex] on a [latex]n+2\,k-v_2(k)\geq n+3[/latex].
Par suite
[TeX]3^{2^n} \equiv 1-2^{n+2} \mod 2^{n+3}[/TeX]

 #9 - 08-12-2015 17:58:58

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

UUn cas particulier de Fermat.

Aussi oui pour cette variante. Tu as achevé en fait ce que je n'avais pas écrit formellement.

Une conséquence de ça, c'est qu'une puissance de 3, si elle est écrite en base 2 et qu'elle comprend 2n chiffres, si on compare le nombre constitué par les  n premiers chiffres avec celui des n derniers, ce sont obligatoirement 2 nombres différents. ...

D'une manière plus générale, j'éprouve un sentiment de profonde ignorance en regardant une puissance de 3 en base 2: Il y a à peu près équilibre entre les 0 et les 1, il y a statistiquement un rapport d'environ 2 entre le nombre de 1 et le nombre de groupes de 1, et on est incapable de prouver quoi que ce soit. On est également incapable de montrer que les écarts entre une puissance de 3 et la puissance de 2 immédiatement supérieure sont à chaque fois différents et globalement en croissance exponentielle.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 63 pommes et que vous en prenez 23, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
19-09-2010 Enigmes Mathématiques
22-01-2012 Enigmes Mathématiques
P2T
Cas de boulets par darkcod03100
25-11-2010 Enigmes Mathématiques
P2T
Moyen Fermat par Vasimolo
05-04-2014 Enigmes Mathématiques
P2T
01-12-2011 Enigmes Mathématiques
P2T
15-05-2011 Enigmes Mathématiques
P2T
Est ce vrai? par kossi_tg
09-08-2013 Enigmes Mathématiques
17-03-2009 Enigmes Mathématiques
P2T
Heure par sibelium
13-07-2012 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete