Enigme Un cas particulier de Fermat. @ Prise2Tete

nodgim · #1

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

nodgim · #2

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

masab · #3

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

La récurrence est terminée !

masab · #4

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

l'entier $3^{2^{n}}-1$ est divisible par $2^{n+2}$ , mais pas par $2^{n+3}$ .

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

nodgim · #5

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

masab · #6

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

nodgim · #7

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.

masab · #8

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

nodgim · #9

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.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

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

Un cas particulier de Ferat.

#0 Pub

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

Un cas particulierr de Fermat.

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

Un cas particulier de FFermat.

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

ub cas particulier de fermat.

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

un cas patticulier de fermat.

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

Un cas particulier de Femrat.

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

Un ccas particulier de Fermat.

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

un cas particulizr de fermat.

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

Un cas particulier de Fermaat.

Réponse rapide

Sujets similaires

Pied de page des forums