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



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.

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 six semaines et a été effectuée par Maxtimax.

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)

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é !!!



Edité 2 fois. La derni&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par AD.

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)

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&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.

\( a= 1, b= -1, p = k = 2 \).

e.v.

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

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&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.

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 [www.wolframalpha.com]

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

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&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par Keynes.

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&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.

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

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)

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&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par LOU16.

$(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



Edité 1 fois. La derni&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par a.bendriouich.

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 v₇ 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$.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 1 fois. La derni&egrave;re correction date de il y a six semaines et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.

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&egrave;re correction date de il y a cinq semaines et a &eacute;t&eacute; effectu&eacute;e par AD.

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: 136 255, Messages: 1 316 873, Utilisateurs: 23 987.
Notre dernier utilisateur inscrit Aybabtu.

---

Ce forum
Discussions: 5 040, Messages: 60 954.