Lien entre pgcd et congruence
dans Arithmétique
Bonjour,
Je souhaite montrer que $PGCD(a,n)=1 \implies a \equiv 1 [n]$.
Mais je ne vois pas comment procéder.
Je souhaite montrer que $PGCD(a,n)=1 \implies a \equiv 1 [n]$.
Mais je ne vois pas comment procéder.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Bézout est ton ami.
Pourtant j'ai lu dans un corrigé que si $a$ et $n$ sont premiers entre eux alors $PGCD(a,n)=1$
Par contre, l'indication de gb et ceci te donneront un résultat qui est vrai, que tu peux essayer de démontrer.
Mais ce n'est pas la même chose que a congru à 1 mod n
désolée ,je n'avais pas vu les messages précédents ...
Bézout assure que « \(a\) et \(n\) sont premiers entre eux » est équivalent à l'existence de deux entiers \(u\) et \(v\) tels que : \(au+nv=1\).
Vu à travers la lunette des congruences, « \(a\) et \(n\) sont premiers entre eux » est équivalent à l'existence d'un entier \(u\) tel que : \(au \equiv 1 \pmod n\), c'est-à-dire à l'inversibilité de \(a\) modulo \(n\), ce qui n'est vraiment pas la congruence que tu évoques.
Le théorème de Bézout se présente comme ça: $\forall (a,b)\in \mathbb{Z}^2,\text{PGCD}(a,n)=1 \leftrightarrow \exists (u,v)\in\mathbb{Z}^2, ua+vn=1$.
Ta confusion vient peut-être d'une petite ressemblance entre $\exists (u,v)\in\mathbb{Z}^2, ua+vn=1$ avec $\exists v\in\mathbb{Z}, a+vn=1$ (qui est équivalente à $a\equiv 1[n]$).
Edit: Oups, pas vu le message de gb, qui dit exactement la même chose, ça va beaucoup trop vite sur ce forum :-D.