Congruence et pgcd

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)$.

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.}$

Re, Je ne comprends toujours pas : "si $p$ divise $c$, alors $p$ divise $k= \displaystyle \prod _{p \mid c,d}p."$

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. }$.