|
#1 - 27-11-2015 08:40:35
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
un cas particulirr 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
#2 - 28-11-2015 20:19:31
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Un cas particulier de Feramt.
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 : 971
Un cas particulier de Fermt.
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 : 971
Un cas particulier de Femat.
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 : 3802
Un cas paarticulier 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 : 971
un cas particylier 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 : 3802
un cas particulier de fetmat.
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 : 971
Un cas particulier de Fermt.
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 : 3802
Un cas particulier e 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.
|
|