Congruences modulo $2^n$
dans Arithmétique
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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ?
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 ?