 |
 
|
 |
|
Congruence
il y a cinq mois
|
|
Membre depuis : il y a cinq mois
Messages: 18
|
Salut. Je cherche des indications pour cette question.
Montrer que : $$
\forall n \in \mathbb{N},~~3^{7^{n}}+ 5^{7^{n}} \equiv ~~1 \pmod { 7^{n+1}}.
$$ Merci pour votre aide
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a quatre années
Messages: 4 022
|
D'où tiens-tu cet énoncé ? ( j'ai écrit un code CamL pour le vérifier et j'ai l'impression que c'est faux pour $n=11$ mais ça fait longtemps que j'ai pas fait de CamL et pour des choses aussi grandes c'est difficile de vérifier à la main je viens de vérifier "à la main" les étapes du calcul et le problème est qu'il y a un overflow donc certains nombres deviennent négatifs parce que ça dépasse la limite donc pas du tout en fait)
"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par Maxtimax.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
A.Bendriouich:
1) Tu peux remarquer que pour $0<k\leq 6, \binom{7}{k}$ est divisible par $7$.
2) Tu peux essayer d'effectuer un raisonnement par récurrence.
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a neuf années
Messages: 1 184
|
On peut le montrer par récurrence mais ce n'est pas facile.
En posant $a=3^{7^n}$ et $a=5^{7^n}$ il faut montrer que $\displaystyle\sum_{k=1}^6{7\choose k}a^kb^{7-k}$ est divisible par $7^{n+2}$ sachant $a+b\equiv 1 \pmod {7^{n+1}}$.
On met $7$ en facteur puis on montre que modulo $7^{n+1}$ on a $ab\equiv1$, $a^2-a+1\equiv0$, $a^3\equiv-1$ et idem pour $b$.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : l’an passé
Messages: 63
|
\begin{align*}
5^{7^{n}}= (7-2)^{7^{n}} = (-2)^{7^{n}} &\equiv-2^{7^{n}} [7^{n+1}] \\
3^{7^{n}} =(7-4)^{7^{n}}&\equiv(-4)^{7^{n}} [7^{n+1}]\equiv-2^{2\times 7^{n}} [7^{n+1}]
\end{align*} Posons $ a=2^{7^{n}}$ alors $ a^{3}=8^{7^{n}}=(1+7)^{7^{n}}\equiv 1[7^{n+1}]$
donc $ (a-1)(a^{2}+a+1) \equiv 0 [7^{n+1}]$
comme $\phi(7^{n+1})\equiv 0 [3]$ alors $ 7^{n+1}\nmid a-1$ $$
a^{2}+a\equiv -1[7^{n+1}]
$$ et c'est gagné !!!
Edité 2 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
Keynes:
On a, sauf erreur, pour tout $p$ premier et $k\geq 1,a,b$ des entiers:
\begin{align}(a+b)^{p^k}\equiv a^{p^k}+b^{p^k}\mod{p^k}\end{align}
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
Soit $n\geq 0$,
De, $3^{7^{n}}+ 5^{7^{n}} \equiv ~~1 \pmod { 7^{n+1}}$ on déduit qu'il existe un entier $k_n$ tel que $3^{7^{n}}=1+7^{n+1}k_n-5^{7^{n}}$.
On élève les deux membres de cette égalité à la puissance $7$ on obtient:
\begin{align}3^{7^{n+1}}&=(1+7^{n+1}k_n-5^{7^{n}})^7\\
&=-5^{7^{n+1}}+(1+7^{n+1}k_n)^7+\sum_{k=1}^6 \binom{7}{k}(1+7^{n+1}k_n)^k(-1)^{7-k}\left(5^{7^{n}}\right)^{7-k}\\
\end{align}
Or, $1+7^{n+1}k_n=3^{7^{n}}+5^{7^{n}}$ donc:
\begin{align}3^{7^{n+1}}+5^{7^{n+1}}&=\left(3^{7^{n}}+5^{7^{n}}\right)^7+\left(3^{7^{n}}+5^{7^{n}}\right)\sum_{k=0}^5 \binom{7}{k+1}\left(3^{7^{n}}+5^{7^{n}}\right)^k(-1)^{6-k}\left(5^{7^{n}}\right)^{6-k}\\\end{align}
Cette égalité et la connaissance du fait que pour tout $0<m<7$ ,$\binom{7}{m}$ est divisible par $7$
Edit:
Ce qui suit est du grand n'importe quoi. Désolé
permet de conclure par récurrence que,sauf erreur, $3^{7^{n+1}}+5^{7^{n+1}}$ est divisible par $7^{n+2}$.
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par Fin de partie.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 11 754
|
\( a= 1, b= -1, p = k = 2 \).
e.v.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a quatre années
Messages: 4 022
|
FindePartie: tu confonds avec $(a+b)^p = a^p+b^p$ mod $p$ pour $p$ premier. Malheureusement ça ne se généralise pas à $p^k$, l'exemple d'ev répondant à cette idée.
Je ne comprends pas la conclusion ton deuxième message.
"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
Je pense que la formule bidon donnée ci-dessus est une confusion avec une formule qui a une apparence semblable sur un corps fini.
Maxtimax:
Est-ce que tu es d'accord sur la validité de la formule? (celle que j'ai obtenue par calcul plus haut)
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par Fin de partie.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a cinq mois
Messages: 18
|
Salut à tous
pouvez vérifier à la main si la formule est vraie pour n=3?
car les logiciels de calcul ne permettent pas de vérifier vu la grandeur des nombres en jeu
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a quatre années
Messages: 4 022
|
Fin de Partie : la formule du binôme de Newton ? à décalage éventuel (je me gourre souvent là dessus ) d'indice près, oui. Mais attention, on n'essaie pas de montrer la divisibilité de $3^{7^{n+1}} + 5^{7^{n+1}}$
a.bendriouich : Je n'en suis pas sûr au vu de mon échec pour $n=11$ et au-dessus mais mon programme CamL disait que ça marchait jusque là, et il y a peu de chance que ce soit une coïncidence. Pour gérer la taille des nombres sur ordi, j'ai fait une exponentiation modulaire (i.e. à chaque étape de la mise à la puissance, je réduis modulo $k$ avec le bon $k$), et il n'y avait pas trop de souci de taille jusqu'à $11$ j'ai l'impression.
"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Congruence
il y a cinq mois
|
|
Membre depuis : l’an passé
Messages: 63
|
Une autre approche de preuve consistera à montrer que :
$$ \forall k \in \{1,2,...7^{n}\} :C_{7^{n}}^{k}7^{k}\equiv 0 [7^{n+1}]$$
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par Keynes.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
Ma formule est correcte (en tout cas sur quelques valeurs cela fonctionne)
Maxtimax:
Je ne comprends pas ce que tu reproches à ce que je pense être une preuve.
A gauche de l'égalité on a $3^{7^{n+1}}+5^{7^{n+1}}$ et à droite on peut factoriser $3^{7^{n}}+5^{7^{n}}$
Si $3^{7^{n}}+5^{7^{n}}$ est divisible par $7^{n+1}$ alors $\left(3^{7^{n}}+5^{7^{n}}\right)^7$ est divisible par $7^{7(n+1)}$
Mais $7(n+1)\geq n+2$ est équivalente à $n \geq -\dfrac{5}{6}$ sauf erreur.
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par Fin de partie.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a quatre années
Messages: 4 022
|
On ne cherche pas à montrer que $3^{7^{n+1}}+5^{7^{n+1}}$ est divisible par $7^{n+2}$ ! il y a un $\equiv 1$ dans la formule ; en particulier dans l'hypothèse de récurrence tu n'as pas "$7^{n+1}$ divise $3^{7^n}+5^{7^n}$"
"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
Oui, en effet. Je m'étais mis en pilotage automatique.
On doit pouvoir malgré tout corriger. Enfin, je l'espère.
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a trois années
Messages: 364
|
Bonsoir,
Il me semble que la résolution de ce problème utilise impérativement le fait que $3$ et $5$ sont des racines $6-\text{èmes}$ primitives de l'unité dans le corps $\Z/7\Z$ où , ou, ce qui revient au même , que ces nombres sont les racines du polynôme $X^2-X+1$ dans ce corps. Ce fait apparait d'ailleurs dans le message de Jandri.
Soit $n \in \N ,\quad a=3^{7^n},\:\: b = 5^{7^n}.\quad $Alors: $a^6\equiv b^6 \equiv 1 \mod 7^{n+1}$
$ a^6-1 \equiv(a^2-1)(a^2 +a+1)(a^2-a+1) \equiv 0 \mod 7^{n+1}$
D'autre part: $(a^2-1) (a^2+a+1) \equiv (3^2-1)(3^2+3+1) \mod7 \implies (a^2-1)(a^2+a+1) \:\text{est inversible dans} \:\Z/7^{n+1}\Z$
On déduit que $a^2-a+1\equiv b^2-b+1 \equiv 0 \mod 7 ^{n+1},\:\:$ puis que:$\:\: (a-b)(a+b-1) \equiv 0 \mod 7^{n+1}.$
Avec, $a-b \not \equiv 0 \mod7$ on conclut :$\quad\boxed {a+b-1 \equiv 0 \mod 7^{n+1}.}$.
Edité 2 fois. La dernière correction date de il y a cinq mois et a été effectuée par LOU16.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : l’an passé
Messages: 63
|
$(2^{7^{n}}-1)(3^{7^{n}}+5^{7^{n}}-1)\equiv (2^{7^{n}}-1)(-4^{7^{n}}-2^{7^{n}}-1)\equiv -(8^{7^{n}}-1)[7^{n+1}]$
Comme $ v_{7}(8^{7^{n}}-1)=v_{7}( (7+1)^{7^{n}}-1) \geq n+1 $ alors
$$ (2^{7^{n}}-1)(3^{7^{n}}+5^{7^{n}}-1)\equiv 0 [7^{n+1}]$$
de plus $ 2^{7^{n}}=2^{(6+1)^{n}}\equiv 2 [7]$ c 'est gagné
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a neuf années
Messages: 1 184
|
Ce résultat ce généralise à tout nombre premier $p$ congru à $1$ modulo $6$.
$-3$ étant alors un carré modulo $p$, il existe un unique couple $(a,b)$ vérifiant $1<a<b<p-1$ et $a+b\equiv ab\equiv 1 \pmod p$.
On montre ensuite par récurrence: $\forall n \in \mathbb{N},~~a^{p^{n}}+ b^{p^{n}} \equiv ~~1 \pmod { p^{n+1}}$
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a neuf années
Messages: 1 184
|
La démonstration directe de Keynes est correcte et elle se généralise à $p$ premier congru à $1$ modulo $6$.
Soit $(a,b)$ avec $1<a<b<p-1$ et $a+b\equiv ab\equiv 1\pmod p$.On en déduit $a^2-a+1\equiv0\pmod p$ puis $a^3\equiv-1\pmod p$.
En posant $c=-a$ on obtient $b\equiv -c^2 \pmod p$.
Par récurrence $a^{p^n}\equiv-c^{p^n}\pmod {p^{n+1}}$ et $b^{p^n}\equiv-c^{2p^n}\pmod {p^{n+1}}$ d'où $a^{p^n}+b^{p^n}-1\equiv -(c^{2p^n}+c^{p^n}+1) \pmod {p^{n+1}}$ puis $(c^{p^n}-1)(a^{p^n}+b^{p^n}-1)\equiv c^{3p^n}-1\pmod {p^{n+1}}$.
De $c^3\equiv 1 \pmod p$ on déduit par récurrence $c^{3p^n}\equiv 1 \pmod {p^{n+1}}$.
Comme $c^{p^n}\equiv c \pmod p$ on obtient finalement $a^{p^n}+b^{p^n}\equiv 1\pmod {p^{n+1}}$.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a cinq mois
Messages: 18
|
Bonjour
et merci
Il me reste à comprendre une justification sur la dernière ligne de Jandri:
pourquoi
$
c^{p^{n}}-1$ est il inversible dans$ Z/p^{n+1}Z ?
$
Merci
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par a.bendriouich.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a neuf années
Messages: 1 184
|
C'est parce que $c^{p^{n}}-1\equiv c-1\pmod p$ et que $c\neq1\pmod p$ puisque $c=-a$ avec $1<a<p-1$.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a deux années
Messages: 35
|
Bonjour,
Malgré des connaissances qui ne sont qu'élémentaires dans ce domaine, j'essaye de comprendre certaines démonstrations. J'ai une petite question :
Que signifie v 7 dans la démonstration de Keynes ?
Merci pour vos réponses
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a onze années
Messages: 17 321
|
Sylvieg : l'exposant de la plus grande puissance de $7$ qui divise un nombre.
Exemple: $\text{v}_7(49)=2$.
Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par Fin de partie.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a deux années
Messages: 35
|
Merci pour la réponse très claire
Je crois avoir compris la démonstration de Keynes.
Elle utilise plusieurs fois ceci :
Si $x$ est congru à $ y $ modulo $7$ alors $$
\forall n \in \mathbb{N},~~x^{7^{n}}
\equiv ~~y^{7^{n}} \pmod { 7^{n+1}}.
$$
Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Congruence
il y a cinq mois
|
|
Membre depuis : il y a neuf années
Messages: 1 184
|
Oui Sylvieg, c'est ce que j'ai utilisé trois fois dans la généralisation de la démonstration de Keynes à un premier de la forme $p=6q+1$.
La démonstration de LOU16 se généralise aussi à un premier de la forme $p=6q+1$.
Il existe un unique couple $(a,b)$ avec $1<a<b<p-1$ et $a+b\equiv ab\equiv 1\pmod p$.
On en déduit $a^2-a+1\equiv 0\pmod p$ puis $a^3\equiv -1\pmod p$.
Je pose $A=a^{p^n}$ et $B=b^{p^n}$. $a^{6q}\equiv1\pmod p$ entraîne $A^{6q}\equiv 1 \pmod{p^{n+1}}$.
Donc $p^{n+1}$ divise $A^{6q}-1=(A-1)(A+1)(A^2-A+1)(A^2+A+1)(1+A^6+A^{12}+...+A^{6(q-1)})$.
Mais $A-1\equiv a-1\not\equiv0\pmod p$, $A+1\equiv a+1\not\equiv0\pmod p$, $A^2+A+1\equiv a^2+a+1\not\equiv0\pmod p$ (car cela entraînerait $a^3\equiv1 \pmod p$), $1+A^6+A^{12}+...+A^{6(q-1)}\equiv 1+a^6+a^{12}+...+a^{6(q-1)}\equiv q\not\equiv 0 \pmod p$.
Donc $p^{n+1}$ divise $A^2-A+1$, donc aussi $BA^2-AB+B$, donc aussi $A+B-1$ puisque $AB=(ab)^{p^n} \equiv 1 \pmod{p^{n+1}}$.
Liste des forums - Statistiques du forum
Total
Discussions: 138 418, Messages: 1 343 977, Utilisateurs: 24 829.
Notre dernier utilisateur inscrit Azaborn.
Ce forum
Discussions: 5 136, Messages: 62 260.
|
|
|
|
 |
 |
 |
©Emmanuel
Vieillard Baron 01-01-2001
|
|