Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
83 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Congruence

Envoyé par a.bendriouich 
Congruence
il y a six semaines
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.
Re: Congruence
il y a six semaines
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.
Re: Congruence
il y a six semaines
avatar
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 six semaines
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 six semaines
\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.
Re: Congruence
il y a six semaines
avatar
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 six semaines
avatar
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é grinning smiley

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.
ev
Re: Congruence
il y a six semaines
avatar
\( a= 1, b= -1, p = k = 2 \).

e.v.
Re: Congruence
il y a six semaines
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 six semaines
avatar
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.
Re: Congruence
il y a six semaines
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 six semaines
@a.bendriouich ça marche pour n=3 voir ici [www.wolframalpha.com]
Re: Congruence
il y a six semaines
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 six semaines
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.
Re: Congruence
il y a six semaines
avatar
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.
Re: Congruence
il y a six semaines
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 six semaines
avatar
Oui, en effet. Je m'étais mis en pilotage automatique. grinning smiley
On doit pouvoir malgré tout corriger. Enfin, je l'espère. smoking smiley

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Congruence
il y a six semaines
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.
Re: Congruence
il y a six semaines
$(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 six semaines
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 six semaines
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 six semaines
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.
Re: Congruence
il y a six semaines
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 six semaines
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 smiling smiley
Re: Congruence
il y a six semaines
avatar
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.
Re: Congruence
il y a cinq semaines
Merci pour la réponse très claire smiling smiley
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.
Re: Congruence
il y a cinq semaines
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}}$.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

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.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page