Congruence et pgcd
dans Arithmétique
Bonjour
Lors d'une lecture, l'auteur part du fait que des entiers relatifs $(a,b,c,d)$ vérifient $ad-bc = 1 [N]$ et conclut qu'il existe des entiers $c',d'$ tels que $c'=c[N]$, $d'=d[N]$ et $pgcd(c',d') = 1$.
C'est allé un peu trop vite pour moi, comment boucher les trous, il y a évidemment du Bézout dedans. Par exemple Bézout nous dit que $(c,d,N)$ sont premiers dans leurs ensemble. Peut-être puis conclure à partir d'ici. Voyez vous ?
Bien à vous.
Lors d'une lecture, l'auteur part du fait que des entiers relatifs $(a,b,c,d)$ vérifient $ad-bc = 1 [N]$ et conclut qu'il existe des entiers $c',d'$ tels que $c'=c[N]$, $d'=d[N]$ et $pgcd(c',d') = 1$.
C'est allé un peu trop vite pour moi, comment boucher les trous, il y a évidemment du Bézout dedans. Par exemple Bézout nous dit que $(c,d,N)$ sont premiers dans leurs ensemble. Peut-être puis conclure à partir d'ici. Voyez vous ?
Bien à vous.
Réponses
-
On peut supposer $c > 1$.
Posons $k:= \displaystyle \prod_{\substack{p \mid c \\ p \nmid d}} p$ et $d^{\, \prime} := d + kN$, et soit $p$ un facteur premier de $c$.
(i) Si $p \nmid d$, alors $\textrm{pgcd}(c,d)=1$ et on peut prendre $(c^{\, \prime} , d^{\, \prime}) = (c,d)$.
(ii) Si $p \mid d$, alors $p \nmid k$, et comme $\textrm{pgcd}(c,d,N) =1$, on a aussi $p \nmid N$. Cela implique que $p \nmid d+kN = d^{\, \prime}$ et donc $\textrm{pgcd}(c,d^{\, \prime})=1$ et on peut prendre $(c^{\, \prime} , d^{\, \prime}) = (c,d+kN)$. -
Ok je vois vous voulez dire pour tout $p$ diviseur premier de $c$ si (i) ... sinon et s'il existe $p$ diviseur de $c$ alors ...
-
Bonjour,
@Noix de Totos. Je ne comprends pas cette phrase :"Soit $p$ un diviseur premier de $c$. Si $p$ ne divise pas $d$, alors $c\wedge d =1."$
@mini_calli. L'affirmation du texte que tu évoques ne me paraît pas aller de soi. En tous cas, je n'ai pas trouvé de justification plus simple que celle-ci :
$\delta:= c\wedge d,\quad c=\delta c_1, \:\:d=\delta d_1, \quad c_1\wedge d_1 =1, \quad \exists u,v\in \Z,\ $ tels que : $uc_1+vd_1 =1.$
L'hypothèse $ad-bc \equiv 1 \mod N$ entraîne que $\ \delta \wedge N=1, \quad \exists q,r \in \Z,\ $ tels que $\ q \delta + rN =1.$
Notons $A =uq+d_1,\ B= vq-c_1.\quad (1)\qquad $ Alors: $\:\:Ac_1+Bd_1=q. \quad (2)\qquad Ac+Bd =\delta q\quad (3).$
Soit $ \varepsilon = A\wedge B.\quad$ D'après $(2), \: \varepsilon \:\text{divise}\: q$ et d'après $(1), \: \varepsilon \:\text{divise}\: d_1$ et $c_1.\quad$ Ainsi :$\:A \wedge B =1, \ \exists x,y \in \Z,\ $ tels que $\ xA+yB=r\quad (4).$
Avec $(3)$ et $(4)$, il vient: $\quad A(c+xN) +B(d+yN)=q\delta + rN =1, \ $ puis : $\:\boxed{ (c+xN) \wedge (d+yN) =1.}$ -
Correction du (i) :
soit $p$ un facteur premier de $c$. Comme $p \mid k$, on a $p \mid \left( d+kN\right) \Longrightarrow p \mid d$. Donc si $p \nmid d$, alors $p \nmid (d+kN)$.
Remarque.
Ce résultat est (le début de) la démonstration de la surjectivité du morphisme de groupes $\textrm{SL}_2(\mathbb{Z}) \to \textrm{SL}_2(\mathbb{Z}/N\mathbb{Z})$, qui, à toute matrice de $\textrm{SL}_2(\mathbb{Z})$, associe la matrice obtenue en réduisant point par point ses éléments modulo $N$. Un morphisme très utilisé en théorie modulaire, notamment son noyau. -
Re, Je ne comprends toujours pas : "si $p$ divise $c$, alors $p$ divise $k= \displaystyle \prod _{p \mid c,d}p."$
-
Si $p$ divise $c$ et $p$ ne divise pas $d$ (c'est le cas (i) traité ici), alors il divise $k$ (par définition de ce $k$), et donc $p$ ne peut pas diviser $d+kN$.
-
Désolé
Je ne comprends vraiment rien.
Avec les hypothèses du $(1)\quad (p \mid c, p \not \mid d)$ , pour quelle raison a-t-on $c\wedge d =1$, de façon à pouvoir prendre $(c',d') = (c,d) $ ou bien pour quelle raison a-t-on $c \wedge d+kN =1? \quad k = \displaystyle \prod_{p\mid c,\: p\not\mid d}p \quad $ (je ne sais pas quelle est la conclusion du $(1)$ que tu cherches à atteindre.)
Je remets à l'endroit ton argument:
Soient $c,d,N $ tels que $c\wedge d\wedge N =1$ et soit $k$ le produit des nombres premiers qui divisent $c$ et ne divisent pas $d$.
Soit $p$ un diviseur premier de $c$.
$1)\quad$ Si $p$ ne divise pas $d$, alors $p$ divise $k$ et donc: $p \wedge( d+kN) =1.$
$2)\quad$ Si $p$ divise $d$, alors $1= p\wedge N= p\wedge k =p\wedge kN =p\wedge (d+kN ).$
Ainsi, pour tout diviseur premier $p$ de $c,\:\:p\wedge( d+kN) =1.\qquad \boxed{ c \wedge( d+kN)=1. }$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres