Congruences

jibounet · July 2017

Bonjour
Je souhaite montrer que $$ 2004^{250k + n} \equiv 2004^n \; [10000] $$ pour tout $k \geq 0$ et tout $n \geq 2$.

J'ai réussi à montrer que $\displaystyle 2004^{250k} \equiv 9376^k \; [10000]$ mais cela ne me permet pas de conclure facilement.
Merci pour votre aide.

depasse · July 2017

Bonsoir,

$10000=2^45^4$
$2004$ est divisible par $4$ donc $2004^2$ par $2^4$

Il suffit donc de prouver que $2004^{250}=1$ modulo $5^4$.
Or $\varphi (5^4)=4\times5^3=500$
Donc (Fermat généralisé) $2004^{500}=1$ modulo $5^4$.
Donc soit $2004^{250}=1$ modulo $5^4$, soit $2004^{250}=-1$ modulo $5^4$.

Par l'absurde:
Si
$2004^{250}=-1$ modulo $5^4$, alors
$2004^{250}=-1$ modulo $5^2$,
$4^{250}=-1$ modulo $5^2$,
$4^{10}=-1$ modulo $5^2$ (car $\varphi (5^2)=4\times5^1=20$, donc $4^{20}=1$ modulo $5^2$ et, par ailleurs, $250=10$ modulo $20$).

Or, air connu, $2^{10}=1024$ et donc $2^{10}=-1$ modulo $25$ et donc $4^{10}=1$ modulo $5^2$.
Contradiction!

Ainsi $2004^{250}=1$ modulo $5^4$, cqfd (ou plutôt cqsd: ce qu'il suffisait de démontrer)

Cordialement
Paul

Edit
Edit: affirmation erronée, au mieux injustifiée. Merci Poirot
Edit: Claude sauve ma preuve: il justifie très joliment mon affirmation pour le moins gratuite jusqu'à son message ci-dessous.

uvdose · July 2017

Bonjour,

En partant de ce qu'a prouvé jibounet, on déduit que $2004^{250k}\equiv1\;(625)$, d'où $2004^{250k}\times501^{n}\equiv501^n\;(625)$. Lorsque $n\geqslant2$, $16$ divise $4^n$, donc $2004^{250k}\times501^{n}\times4^n\equiv501^n\times4^n\;(625\times16)$, d'où la congruence cherchée.

jibounet · July 2017

Super merci !

Poirot · July 2017

@depasse : comment passes-tu de $2004^{500}=1 \pmod 5^4$ à $2004^{250}= \pm1 \pmod 5^4$ ? Dans $\mathbb Z/8\mathbb Z$, $3^2=1$ sans que $3= \pm 1$.

depasse · July 2017

@Poirot
Tu as tout à fait raison! Le pire c'est que j'ai dénoncé cette erreur dans le raisonnement de l'un d'entre nous il n'y a pas longtemps!

claude quitté · July 2017

@Paul (et Poirot)
Pour vous ``rassurer''. Soit $A$ un anneau local dans lequel 2 est inversible. Alors, dans $A$, $x^2 = 1 \Rightarrow x = \pm 1$. En effet, l'hypothèse s'écrit $(1-x)(1+x) = 0$ et l'on a $(1-x) + (1+x) = 2$ inversible. Comme l'anneau est local, ou bien $1-x$ est inversible auquel cas $x = -1$ ou bien $1+x$ est inversible, auquel cas $x=1$.

Cas particulier : $A = \Z/p^k\Z$ avec $p$ premier impair et $k \ge 1$.

depasse · July 2017

@ Claude
Un grand merci pour ton élégante démonstration.
Amicalement
Paul

Poirot · July 2017

Merci Claude pour ce joli argument !

Congruences

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 28