Congruence
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
Montrer que : $$
\forall n \in \mathbb{N},~~3^{7^{n}}+ 5^{7^{n}} \equiv ~~1 \pmod { 7^{n+1}}.
$$ Merci pour votre aide
Réponses
-
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)
-
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. -
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$. -
\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é !!! -
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} -
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é :-D
permet de conclure par récurrence que,sauf erreur, $3^{7^{n+1}}+5^{7^{n+1}}$ est divisible par $7^{n+2}$. -
\( a= 1, b= -1, p = k = 2 \).
e.v.Personne n'a raison contre un enfant qui pleure. -
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. -
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) -
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 -
@a.bendriouich ça marche pour n=3 voir ici https://www.wolframalpha.com/input/?i=3^(7^3)+5^(7^3)+mod+7^4
-
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. -
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}]$$ -
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. -
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}$"
-
Oui, en effet. Je m'étais mis en pilotage automatique. :-D
On doit pouvoir malgré tout corriger. Enfin, je l'espère. B-)- -
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}.}$. -
$(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é -
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}}$ -
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}}$. -
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 -
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$.
-
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 v7 dans la démonstration de Keynes ?
Merci pour vos réponses :-) -
Sylvieg : l'exposant de la plus grande puissance de $7$ qui divise un nombre.
Exemple: $\text{v}_7(49)=2$. -
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}}.
$$ -
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}}$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres