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

Un cas particulier dde 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 : 3577

Un cas particuier de Fermat.

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

Un cas particuliier de Fermat.

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

un cas partixulier 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 : 3577

un cas particilier 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 : 814

Un cas particulier de Feermat.

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

un cas particulier de fzrmat.

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

un vas particulier 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 : 3577

Un cas particulier de Ferat.

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 à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

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