Congruences modulo $2^n$

Julia Paule · March 2021

Bonjour,

Je remarque qu'on a :
$q^2 \equiv 1 (\mod 8) \Leftrightarrow q = \pm 1 (\mod 4)$, et
$q^2 \equiv 1 (\mod 16) \Leftrightarrow q = \pm 1 (\mod 8)$.

Cela peut-il se généraliser en :
$q^2 \equiv 1 (\mod 2^{n+1}) \Leftrightarrow q = \pm 1 (\mod 2^n)$ ?
et même en :
$q^2 \equiv r^2(\mod 2^{n+1}) \Leftrightarrow q = \pm r (\mod 2^n)$ ?
Un sens est évident, la réciproque me le parait moins.

Merci d'avance.

JLT · March 2021

Avec $q^2-r^2$ ça ne risque pas de marcher car $4^2-0^2$ est divisible par $16$ mais $4-0$ et $4+0$ ne sont pas divisibles par $8$.

Pour $q^2-1$ tu peux nous montrer ta démonstration du sens évident, et nous dire pourquoi ta démonstration coince pour la réciproque ?

Julia Paule · March 2021

Merci JLT.

Le sens évident : $q \equiv \pm 1 (\mod 2^n) \Rightarrow q^2 \equiv 1 (\mod 2^{n+1})$ :

$q \equiv \pm 1 (\mod 2^n) \Rightarrow q=k.2^n \pm 1 \Rightarrow q^2=(k.2^n \pm 1)^2=k^2.2^{2n} \pm 2k.2^n +1 \equiv 1 ( \mod 2^{n+1})$.

Dans l'autre sens : $q^2 \equiv 1 (\mod 2^{n+1}) \Rightarrow 2^{n+1} \mid (q-1)(q+1)$, cela n'aboutit pas.
Avec la même démarche que l'autre : $q^2=1+k.2^{n+1}=(1+k.2^n)^2 - k^2 . 2^{2n}$.
Alors $2^{2n} \mid (q-(1+k.2^n))(q+(1+k.2^n))$. Donc $2^n$ divise l'un ou l'autre des facteurs, et c'est gagné. Merci !

Il y a sûrement plus simple, non ?

JLT · March 2021

On peut aussi raisonner ainsi : $2^{n+1}\mid (q-1)(q+1)$ donc $(q-1)(q+1)$ est pair. Comme $q-1$ et $q+1$ ont la même parité, ils sont tous les deux pairs. Mais $(q+1)-(q-1)=2$ donc ils ne peuvent pas être tous deux divisibles par $4$. Si par exemple $q+1$ n'est pas divisible par $4$ alors $2^n\mid (q-1)\times \frac{q+1}{2}$ et $2^n$ est premier avec $\frac{q+1}{2}$ donc $2^n\mid q-1$.

Julia Paule · March 2021

Super JLT, ça marche.

Congruences modulo $2^n$

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 35